BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Xujin Chen (Chinese Academy of Sciences)
DTSTART:20201217T070000Z
DTEND:20201217T080000Z
DTSTAMP:20260423T021014Z
UID:SCMSComb/24
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SCMSComb/24/
 ">Ranking Tournaments with No Errors</a>\nby Xujin Chen (Chinese Academy o
 f Sciences) as part of SCMS Combinatorics Seminar\n\n\nAbstract\nWe examin
 e the classical problem of ranking a set of players on the basis of a set 
 of\npairwise comparisons arising from a sports tournament\, with the objec
 tive of minimizing the total number of upsets\,\nwhere an upset occurs if 
 a higher ranked player was actually defeated by a lower ranked player. Thi
 s problem\ncan be rephrased as the so-called minimum feedback arc set prob
 lem on tournaments\, which arises in a rich variety\nof applications and h
 as been a subject of extensive research. We study this NP-hard problem usi
 ng\nstructure-driven and linear programming approaches.\n\nLet $T=(V\,A)$ 
 be a tournament with a nonnegative integral weight\n$w(e)$ on each arc $e$
 . A subset $F$ of arcs is called a feedback arc set if $T\\setminus F$ con
 tains no cycles\n(directed). A collection $C$ of cycles (with repetition a
 llowed) is called a cycle packing if each arc\n$e$ is used at most $w(e)$ 
 times by members of $C$.  We call $T$ cycle Mengerian if\, for every nonne
 gative\nintegral function ${w}$ defined on $A$\, the minimum total weight 
 of a feedback arc set is equal to the maximum\nsize of a cycle packing. In
  this talk\, we\nwill discuss the characterization that a tournament is cy
 cle Mengerian if and only if it contains none of\nfour Möbius ladders as 
 a subgraph. (Joint work with Guoli Ding\, Wenan Zang\, and Qiulan Zhao.)\n
 \npw 121323\n
LOCATION:https://researchseminars.org/talk/SCMSComb/24/
END:VEVENT
END:VCALENDAR