\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for Garth Isaak, Tournaments as Feedback Arc Sets

We examine the size $s(n)$ of a smallest tournament having the arcs
of an acyclic
tournament on $n$ vertices as a minimum feedback arc set. Using an
integer linear programming formulation we obtain
lower bounds $s(n) \geq 3n - 2 - \lfloor \log_2 n \rfloor$ or
$s(n) \geq 3n - 1 - \lfloor \log_2 n \rfloor$, depending on the binary
expansion of $n$. When $n = 2^k - 2^t$ we show that the bounds are
tight with $s(n) = 3n - 2 - \lfloor \log_2 n \rfloor$. One view of this
problem is that if the `teams' in a tournament are ranked to minimize
inconsistencies there is some tournament with $s(n)$ `teams' in which
$n$ are ranked wrong. We will also pose some questions about conditions
on feedback arc sets, motivated by our proofs, which ensure equality
between the maximum number of arc disjoint cycles and the minimum
size of a feedback arc set in a tournament. 

\bye