% Final version of a LaTeX file for an 19 page document.
\documentstyle[12pt]{article}
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{6in}
\newtheorem{tdef}{Definition}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{rmk}{Remark}
\newcommand{\fas}{minimum feedback arc set}
\date{Submitted: April 21, 1995; Accepted: October 3, 1995}
\title{Tournaments as Feedback Arc Sets}
\author{Garth Isaak\thanks{Partially supported by a grant from
the ONR} \\ Department of Mathematics \\ Lehigh University,
Bethlehem, PA 18015 \\
gi02@lehigh.edu}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 2 (1995),
\#R20\hfill}
\thispagestyle{empty}
\begin{document}
\maketitle
\begin{abstract}
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. \\
{\bf AMS Classification: Primary 05C20; Secondary 68R10 }
\end{abstract}
\section{Introduction}
A feedback arc set in a digraph is a set of arcs whose removal makes
the digraph acyclic. J.P.\ Barthelemy asked whether every acyclic
digraph arises as the arcs of a minimum sized feedback arc set of some
tournament. In [\ref{bhirt}] we showed that this was the case and
examined the smallest (vertex) size of such a tournament. For a digraph on $n$
vertices, this size is at most $s(n)$ where $s(n)$ is the smallest
size of a tournament with `the' acyclic tournament $T_n$ on $n$
vertices as a feedback arc set.
(In [\ref{bhirt}] we used the term reversing number, which is the
number of additional vertices, i.e., $s(n) - n$.)
In Section \ref{ilp} we will review an integer linear programming
formulation (from [\ref{bhirt}]) and sketch a proof that $s(n)$ is
determined by its optimal value. We obtain lower bounds on $s(n)$ in
Section \ref{lb} and exact values in Section \ref{exv}. These can be
summarized as \vspace{\baselineskip} \\
{\bf Theorem} {\it
\[ s(n) \geq 3n - 2 - \left\lfloor \log_2 n \right\rfloor \]
if $n$ is Type I or III and
\[ s(n) \geq 3n - 1 - \left\lfloor \log_2 n \right\rfloor \]
if $n$ is Type II. \\
Furthermore, if $n = 2^k - 2^t$ then
\[ s(n) = 3n - 2 - \left\lfloor \log_2 n
\right\rfloor. \] }
The definitions of Types I,II,III will be given in Section \ref{lb}.
Further upper bounds on $s(n)$ will also be discussed in
Section \ref{exv}.
We conjecture that $s(n)$ is equal to the lower bounds above for all
$n$. One way of proving the upper bounds on $s(n)$ involves filling
in an upper triangular array with ordered pairs subject to a Latin
Square like condition and another condition, with
$3n - 2 - \left\lfloor \log_2 n \right\rfloor$ or
$3n - 1 - \left\lfloor \log_2 n \right\rfloor$ pairs.
This will be discussed in Section \ref{exv}.
Our proofs of upper bounds on $s(n)$ construct collections of arc
disjoint cycles in a tournament with size equal to the the number of
arcs in a minimum feedback arc set. In general this equality does not
hold. In Section \ref{adc}, we briefly discuss the problem of determining
conditions on feedback arc sets that ensure equality. For example,
if a tournament has a path as a feedback arc set
then equality holds. \vspace{\baselineskip} \\
{\bf Conjecture} {\it If $T$ is a tournament with a minimum feedback arc set
a set of arcs which form a (smaller) acyclic tournament
then the maximum number of arc disjoint cycles in $T$
equals the minimum size of a feedback arc set. } \\
The upper bound proofs in Section \ref{exv} show that this is true
for certain tournaments $T$ and suggest that it is true in general.
The problem we discuss can be viewed in the following manner. If the
`teams' in a tournament are ranked so as to minimize the number of
inconsistencies what patterns can these inconsistencies form?
The result of [\ref{bhirt}] mentioned above shows that every acyclic
digraph can arise in such a manner. In particular, there exist
tournaments on $s(n)$ `teams' for which $n$ `teams' are ranked wrong.
For these $n$ `teams', $i$ is ranked ahead of $j$ exactly when $j$
`beats' $i$.
For contrast to the problem considered here,
we could also consider weighted version of feedback arc
sets. In this case, each deleted arc is assigned a weight equal to
the distance between its endpoints in the unique acyclic
ordering after the feedback arc set is deleted. (There is a unique
ordering if the original digraph is a tournament.) An ordering which
minimizes the weighted sum of deleted arcs is equivalent to ranking
based on non-increasing outdegrees (i.e., score sequence).
While all acyclic tournaments arise as feedback arc sets,
the only tournament that arises as a feedback arc set in this
weighted version is the tournament on two vertices. See
[\ref{it}] for details. For a related variation see [\ref{gu}].
\section{An Integer Programming Formulation} \label{ilp}
In [\ref{bhirt}] we examined a particular integer linear programming
problem which provided a lower bound on $s(n)$. We
speculated that perhaps this bound was tight. In this section we
reintroduce the integer program and sketch a proof that indeed its
solution does determine $s(n)$.
There are many equivalent versions of the problem of finding a
minimum feedback arc set. An early reference is [\ref{yg}].
See [\ref{jung}] for a good summary of
these variations. We will be interested in the following version.
Given a tournament $T$, find an ordering $\pi$ of its vertices
which minimizes the number inconsistencies;
$\pi(i) < \pi(j)$ with $(j,i) \in A(T)$. (Where $A(T)$ is the arc set
of $T$.) The inconsistent arcs are a minimum size feedback arc set.
Conversely, after removing the arcs of a minimum feedback arc set
in a tournament, the remaining graph is acyclic and has a unique
acyclic ordering (i.e., it contains a Hamiltonian path). This
ordering minimizes inconsistencies.
We now describe tournaments $T(\vec x,n)$ which have the acyclic
tournament $T_n$ as a feedback arc set. Any tournament which has
$T_n$ as a feedback arc set will be of this form for some $\vec x$.
We will then describe conditions on the $x_i$ necessary for
$T_n$ to be a minimum sized feedback arc set in $T(\vec x,n)$.
Minimizing $\sum x_i$ subject to these conditions gives a lower
bound on $s(n)$. In fact, it turns out that the conditions are also
sufficient so that the integer linear program minimizing
$\sum x_i$ subject to the conditions has $s(n)-n$ as an optimal
solution.
Any tournament with $T_n$ as a feedback arc set can be completely
described in terms of the numbers of
vertices between two vertices of $T_n$ in the ordering minimizing
inconsistencies. Let $V(T_n) = \{v_1, v_2, \ldots v_n\}$ be the
vertices of $T_n$ with $A(T_n) = \{ (v_j,v_i)| j > i\}$.
The vertex set of $T(\vec x,n)$ is
\[ V(T_n) \cup
\{ u_{i,j} | 1 \leq i \leq n-1, 1 \leq j \leq x_i \}. \]
The arcs of $T(\vec x,n)$ are
\[ A(T_n) \cup
\{ (u_{i,j},u_{s,t}) : i < s \mbox { or } i = s \mbox { and }
j < t \} \cup \{ (v_i,u_{s,t}) | i \leq s \} \cup
\{ (u_{i,j},v_s) | i < s\}. \]
We can think of $T(\vec x,n)$ in the following manner. The vertex set is
$V(T_n)$ along with `extra' vertices $u_{i,j}$ specified by
$\vec x$. The arcs are those consistent with the ordering
\[ v_1, u_{1,1}, \ldots, u_{1,x_1}, v_2,
u_{2,1} \ldots, u_{2,x_2}, v_3, \ldots, v_{n-1}, u_{n-1,1}, \ldots,
u_{n-1,x_{n-1}}, v_n \] except for arcs between $v_i$ vertices which
are inconsistent with the ordering. We will call this the defining
ordering of $T(\vec x,n)$. If
$U_i$ represents $u_{i,1}, u_{i,2}, \ldots, u_{i,x_i}$
the the defining ordering looks like
\[ v_1,U_1,v_2,U_2, \ldots, v_{n-1},U_{n-1},v_n. \]
Clearly, $A(T_n)$ is a feedback
arc set in $T(\vec x,n)$ since it is the set of arcs inconsistent
with the defining ordering.
Note that $n + \sum_{i=1}^{n-1} x_i$ is the number of vertices in
$T(\vec x,n)$. Thus to determine $s(n)$ we must find $x_i$ with
minimum $\sum_{i=1}^{n-1} x_i$ such that $T(\vec x,n)$ has $T_n$ as
a minimum feedback arc set.
If the defining ordering minimizes inconsistencies then for any
other ordering the number of inconsistencies must be at least
$|A(T_n)| = {n \choose 2}$. With $m = \lfloor n/2 \rfloor$
one `bad' ordering is
\[ U_1, U_2, \ldots, U_m, v_n, v_{n-1}, \ldots, v_3, v_2, v_1,
U_{m+1}, \ldots, U_{n-1}. \]
So we maintain the ordering of the $u_{i,j}$ and shift
the $v_i$ to the `middle' and reverse their order.
The arcs $(v_s,u_{i,j})$ for $s \leq i \leq m$ are reversed as are
arcs $(u_{i,j},v_s)$ for $m + 1 \leq i < s$. So
the number of inconsistent arcs is
\[ x_1 + 2x_2 + 3x_3 + \cdots + \frac{n}{2}x_{n/2} +
(\frac{n}{2} -1)x_{n/2+1} + \cdots + 2x_{n-2} + x_{n-1} \]
if $n$ is even and
\[ x_1 + 2x_2 + 3x_3 + \cdots + \left\lfloor \frac{n}{2}
\right\rfloor x_{\lfloor n/2 \rfloor} +
\left\lfloor \frac{n}{2} \right\rfloor
x_{\lfloor n/2 \rfloor +1} + \cdots + 2x_{n-2} + x_{n-1} \]
if $n$ is odd.
These sums must be at least ${n \choose 2}$ in order for the
defining ordering to minimize inconsistencies.
We can also obtain a `bad' ordering by restricting the ordering
above to a segment of $T(\vec x,n)$ from $v_j$ to $v_{j + h}$.
For example, the ordering
\[ v_1, U_1, v_2, U_2, U_3, U_4, U_5, v_9, v_8, v_7, v_6, v_5, v_4,
v_3, U_6, U_7, U_8, U_9, v_{10} \ldots \] yields the inequality
$x_3 + 2x_4 + 3x_5 + 3x_6 + 2x_7 + x_8 \geq {7 \choose 2}$
for any $n \geq 10$.
So the $x_i$ must satisfy
\begin{equation} \label{lb1o}
\sum_{i=1}^{(h-j)/2} i(x_{j+i-1} + x_{h-i}) \geq {h-j+1 \choose 2}
\mbox{ for $h-j$ even} \end{equation}
and
\begin{equation} \label{lb1e}
\left( \sum_{i=1}^{(h-j-1)/2} i(x_{j+i-1} + x_{h-i}) \right) +
\frac{h-j+1}{2}x_{j + (h-j-1)/2} \geq {h-j+1 \choose 2}
\mbox{ for $h-j$ odd} \end{equation} \\
where the $\sum$ term is interpreted as $0$ if $h-j = 1$.
More details can be found in [\ref{bhirt}].
\begin{tdef} Let ILP(n) be
the integer linear program, $\min \sum_{i=1}^{n-1} x_i$ subject to
(\ref{lb1o}), (\ref{lb1e}) and $x_i$ integral.
\end{tdef}
Note that if $I(n)$ is the optimal value to ILP(n) then
$s(n) \geq n + I(n)$. In [\ref{bhirt}] we asked if equality holds.
We can in fact show this. However, since the details are lengthy
and since only the lower bound is needed for what follows, we will
not include the proof here.
\section{Lower Bounds} \label{lb}
In this section we determine lower bounds on the value of the integer
linear programming problem (ILP) of the previous section. We will use
the idea of cutting planes. The ideas are similar to those used in
[\ref{bhirt}] however we use a more careful analysis and we believe that
the lower bounds obtained here in fact give the value of ILP.
We will show in Section \ref{exv} that this is the case for
$n = 2^k - 2^t$.
First, we get a lower bound on $\sum_{i=1}^{n-1} ix_{j+i-1}$ and
also on $\sum_{i=1}^{n-1} ix_{j-i}$.
\begin{tdef}
Let $S(1) = 0$ and $S(2) = 1$ for $n \geq 3$
\[ S(n) = {n \choose 2} + S\left(\left\lfloor \frac{n}{2}
\right\rfloor\right) +
S\left(\left\lceil \frac{n}{2} \right\rceil\right). \]
\end{tdef}
\begin{lem}
For $x_i$ as in ILP and any $j$ such that the $x$ variables
below are defined,
\begin{equation} \label{lft}
\sum_{i=1}^{n-1} ix_{j+i-1} \geq S(n) \end{equation}
and \begin{equation} \label{rgt}
\sum_{i=1}^{n-1} ix_{j-i} \geq S(n). \end{equation}
\end{lem}
Proof: For ease of notation we prove
$\sum_{i=1}^{n-1} ix_i \geq S(n)$. The general cases of
(\ref{lft}) and (\ref{rgt}) follow by
the symmetry of (\ref{lb1o}) and (\ref{lb1e}).
The proof is by induction on $n$. For $n = 2$ this is just
(\ref{lb1e}).
For $n$ even combine
\[ \left( \sum_{i=1}^{(n-2)/2} i(x_i + x_{n-i}) \right)
+ \frac{n}{2} x_{\frac{n}{2}} \geq {n \choose 2} \]
from (\ref{lb1e}) with $j=1$ and $h=n$ and
\[ 2\sum_{i=1}^{(n/2) -1} ix_{\frac{n}{2} +i}
\geq 2S\left( \frac{n}{2} \right) \]
from induction on (\ref{lft}) with $j = \frac{n}{2} + 1$
to get
\[ \sum_{i=1}^{n-1} ix_i \geq {n \choose 2}
+ 2S\left( \frac{n}{2} \right) = S(n). \]
For $n$ odd combine
\[ \sum_{i=1}^{(n-1)/2} i(x_i + x_{n-i}) \geq {n \choose 2} \]
from (\ref{lb1o}) with $j=1$ and $h = n$ and
\[ \sum_{i=1}^{\frac{n+1}{2}-1} ix_{\frac{n-1}{2} + i}
\geq S\left(\frac{n+1}{2} \right) \]
from induction on (\ref{lft}) with $j = \frac{n+1}{2}$ and
\[ \sum_{i=1}^{\frac{n-1}{2}-1} ix_{\frac{n+1}{2}+i} \geq
S\left( \frac{n-1}{2} \right) \]
from induction on (\ref{lft}) with $j = \frac{n+3}{2}$
to get
\[ \sum_{i=1}^{n-1} ix_i \geq {n \choose 2}
+ S\left( \frac{n-1}{2} \right) +
S\left( \frac{n+1}{2} \right) = S(n). \Box \]
For example, the Lemma gives
$5x_1 + 4x_2 + 3x_3 + 2x_4 + x_5 \geq S(6)$. It also gives
$x_3 + 2x_4 + 3x_5 + 4x_6 + 5x_7 + 6x_8 \geq S(7)$ from combining
$x_3 + 2x_4 + 3x_5 + 3x_6 + 2x_7 + x_8 \geq {7 \choose 2}$ with
$x_6 + 2x_7 + 3x_8 \geq S(4)$ and $x_7 + 2x_8 \geq S(3)$.
We classify each integer $n$ as
one of four types. Let $k = \left\lfloor \log_2 n \right\rfloor$.
\begin{itemize}
\item Type I: $n = 2^k + 2^{k-2} + \cdots + 2^{k - 2t}$ for
some $0 \leq t \leq \left\lfloor k/2 \right\rfloor$.
\item Type II: $2^k < n < 2^k + 2^{k-2} + \cdots +
2^{k - 2\left\lfloor k/2 \right\rfloor}$ and $n$ not of type I.
\item Type III:
$n > 2^k + 2^{k-2} + \cdots + 2^{k - 2\left\lfloor k/2 \right\rfloor}$.
\item Type IVo:
$n = 2^k + 2^{k-2} + \cdots + 2^3 + 2 + 1$ for $k$ odd.
\item Type IVe:
$n = 2^k + 2^{k-2} + \cdots + 2^2 + 2^0 + 1$ for $k$ even,
$k \geq 2$.
\end{itemize}
Types IVo and IVe are needed only as intermediate steps in
Lemma \ref{ess} and Theorem \ref{tlb}. Hence
Types IVo and IVe are also included in Type III to ease the statement
of Theorem \ref{tlb}.
\begin{lem} \label{ess}
If $n$ is of Type I then
\( {\displaystyle
S(n) = n^2 - n - \frac{n}{2} \left\lfloor \log_2 n \right\rfloor}\).
If $n$ is of Type II then
\( {\displaystyle S(n) >
n^2 - n - \frac{n}{2} \left\lfloor \log_2 n \right\rfloor}\).
If $n$ is of Type III then
\( {\displaystyle S(n) > n^2 - \frac{3n}{2} -
\frac{n}{2} \left\lfloor \log_2 n \right\rfloor}\).
If $n$ is of Type IVo then
\( {\displaystyle S(n) =
n^2 - n - \frac{n}{2} \left\lfloor \log_2 n \right\rfloor - \frac{1}{2} }\).
If $n$ is of Type IVe then
\( {\displaystyle S(n) =
n^2 - n - \frac{n}{2} \left\lfloor \log_2 n \right\rfloor - 1} \).
\end{lem}
Proof: We use induction. It is easy to check the necessary base cases
$n = 1,2,3$. (The case $n=3$ must be checked separately
since in this case $n=2 = 2^0 + 1$ would be assumed to be Type IVe
in the inductive step, but $n =2$ is excluded from Type IVe since
$k=0$.) Observe also, that the bounds for Types IVo and IVe imply
those for Type III. So when proving the bound for Type III we will
not check those values that are also Type IVo or IVe.
There are a number of cases to check, all quite similar.
Throughout this proof we will use
$k = \left\lfloor \log_2 n \right\rfloor$.
Let $T(n) = n^2 - n - \frac{n}{2}k$.
Then for even $n$
\begin{eqnarray}
{n \choose 2} + T\left(\left\lfloor \frac{n}{2}
\right\rfloor\right) +
T\left(\left\lceil \frac{n}{2} \right\rceil\right) & = &
{n \choose 2} + 2\left[ \left(\frac{n}{2}
\right)^2 - \left( \frac{n}{2} \right) -
\left( \frac{n}{4} \right)(k-1)\right] \nonumber \\
& = & n^2 - n - \frac{n}{2}k. \label{eqs1}
\end{eqnarray}
For odd $n \not = 2^{k+1}-1$
\begin{eqnarray}
{n \choose 2} + T\left(\left\lfloor \frac{n}{2}
\right\rfloor\right) +
T\left(\left\lceil \frac{n}{2} \right\rceil\right) & = &
{n \choose 2} + \left[ \left(\frac{n-1}{2}
\right)^2 - \left( \frac{n-1}{2} \right) -
\left( \frac{n-1}{4} \right)(k-1)\right] \nonumber \\
& & \mbox{} +
\left[ \left(\frac{n+1}{2}
\right)^2 - \left( \frac{n+1}{2} \right) -
\left( \frac{n+1}{4} \right)(k-1)\right] \nonumber \\
& = & n^2 - n - \frac{n}{2}k + \frac{1}{2}. \label{eqs2}
\end{eqnarray}
Case 1a: $n$ is even and Type 1. Then $\frac{n}{2}$ is also Type I
and \[ S(n) = {n \choose 2} + 2S\left(\frac{n}{2}\right) =
{n \choose 2} + 2T\left(\frac{n}{2}\right) = n^2 - n - \frac{n}{2}k\] by
induction and (\ref{eqs1}).
Case 1b: $n$ is odd and Type 1. Then $\frac{n-1}{2}$ is Type I and
$\frac{n+1}{2}$ is Type IVo. So
\begin{eqnarray*} S(n) & = &
{n \choose 2} + S\left(\frac{n-1}{2}\right)
+ S\left(\frac{n+1}{2}\right) \\
& = & {n \choose 2} + T\left(\frac{n-1}{2}\right)
+ \left(T\left(\frac{n+1}{2}\right)
- \frac{1}{2}\right) \\
& = & n^2 - n - \frac{n}{2}k \end{eqnarray*}
by induction and (\ref{eqs2}).
Case 2: $n$ is of Type II. Then $\left\lfloor \frac{n}{2} \right\rfloor$ and
$\left\lceil \frac{n}{2} \right\rceil$ are either Type I or Type II
and at least
one is Type II. So \[ S(n) = {n \choose 2} +
S\left(\left\lfloor \frac{n}{2} \right\rfloor\right) +
S\left(\left\lceil \frac{n}{2}
\right\rceil\right) >
{n \choose 2} + T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) +
T\left(\left\lceil \frac{n}{2} \right\rceil\right) \geq n^2 - n - \frac{n}{2}k
\] by induction
and (\ref{eqs1}) and (\ref{eqs2}).
Case 3a: $n$ is of Type III and not of Type IVo or IVe and also
$n \not = 2^{k+1} - 1$. Then $\left\lfloor \frac{n}{2} \right\rfloor$ and
$\left\lceil \frac{n}{2} \right\rceil$ are also Type III.
So \begin{eqnarray*} S(n) & = & {n \choose 2} +
S\left(\left\lfloor \frac{n}{2} \right\rfloor\right) +
S\left(\left\lceil \frac{n}{2}
\right\rceil\right) \\ & > &
{n \choose 2} + \left(T\left(\left\lfloor \frac{n}{2} \right\rfloor\right)
- \frac{1}{2} \left\lfloor \frac{n}{2} \right\rfloor \right) +
\left( T\left(\left\lceil \frac{n}{2} \right\rceil\right) -
\frac{1}{2} \left\lceil \frac{n}{2} \right\rceil \right) \\
& \geq & n^2 - n - \frac{n}{2}k -
\frac{1}{2} \left\lfloor \frac{n}{2} \right\rfloor -
\frac{1}{2} \left\lceil \frac{n}{2} \right\rceil \\
& = & n^2 - \frac{3}{2}n -
\frac{n}{2}k \end{eqnarray*} by induction
and (\ref{eqs1}) and (\ref{eqs2}).
Case 3b: $n = 2^{k+1} -1$. Then $\left\lfloor \frac{n}{2} \right\rfloor =
2^k - 1$ is Type III and $\left\lceil \frac{n}{2} \right\rceil =
2^k$ is Type I. So
\begin{eqnarray*} S(n) & = & {n \choose 2} +
S\left(\left\lfloor \frac{n}{2} \right\rfloor\right) +
S\left(\left\lceil \frac{n}{2}
\right\rceil\right) \\
& > & {n \choose 2} + \left( \frac{n-1}{2}^2 - \frac{3}{2}\left(
\frac{n-1}{2}\right) - \frac{n-1}{4}(k-1) \right) +
\left( \frac{n+1}{2}^2 - \frac{n+1}{2} - \frac{n+1}{4}k \right) \\
& = & n^2 - \frac{3}{2}n + \frac{1}{2} - \frac{n}{2}k \\
& > & n^2 - \frac{3}{2}n - \frac{n}{2}k \end{eqnarray*}
by induction.
Case 4a: $n$ is Type IVe. Then $\frac{n}{2}$
is Type IVo. So
\[ S(n) = {n \choose 2} +
2S\left(\frac{n}{2}\right)
= {n \choose 2} + 2\left( T\left(\frac{n}{2}\right) - \frac{1}{2}
\right) =
n^2 - n - \frac{n}{2}k - 1\]
by induction and (\ref{eqs1}).
Case 4b: $n$ is Type IVo. Then $\left\lfloor \frac{n}{2} \right\rfloor$
is Type I and $\left\lceil \frac{n}{2} \right\rceil$ is Type IVe. So
\begin{eqnarray*} S(n) & = & {n \choose 2} +
S\left(\left\lfloor \frac{n}{2} \right\rfloor\right) +
S\left(\left\lceil \frac{n}{2}
\right\rceil\right) \\
& = & {n \choose 2} + T\left(\frac{n-1}{2}\right) +
\left( T\left(\frac{n+1}{2}\right) - 1 \right) \\ & = &
n^2 - n - \frac{n}{2} + \frac{1}{2} - 1 \\ & = &
n^2 - n - \frac{n}{2} - \frac{1}{2} \end{eqnarray*}
by induction and (\ref{eqs2}).
$\Box$
If $\alpha(n)$ denotes the exponent of the highest power of
2 dividing $n$ then $S(n+1) - 2S(n) + S(n-1) = \alpha(n)+1$
[\ref{glenn}]. From this we get
$S(n) = \sum_{i=1}^{n-1} (n-i)(\alpha(i)+1)$. This may be useful
in obtaining more exact estimates of $S(n)$. However, for our
purposes, examining upper bounds on $S(n)$ indicates that
improved values will not change the results of
Theorem \ref{tlb} based on the bounds of Lemma \ref{ess}.
The next Theorem improves the lower bound $\sum_{i=1}^{n-1} x_i
\geq 2n - 4 \lfloor \log_2 n \rfloor$ obtained in [\ref{bhirt}].
\begin{thm} \label{tlb}
For $x_i$ as in ILP,
$\sum_{i=1}^{n-1} x_i \geq 2n - 2 - \left\lfloor \log_2 n \right\rfloor$
if $n$ is Type I or III and
$\sum_{i=1}^{n-1} x_i \geq
2n - 1 - \left\lfloor \log_2 n \right\rfloor$ if $n$ is Type II.
\end{thm}
Proof: As in the proof of Lemma \ref{ess}, there are a number of
cases to check, all quite similar. In each case we combine
an inequality (\ref{lb1o}) or (\ref{lb1e}) with an inequality
(\ref{lft}) and an inequality (\ref{rgt}) to get a lower bound for
$\sum_{i=1}^{n-1} x_i$ in terms $S(n)$. Then we use the bounds on
$S(n)$ from Lemma \ref{ess} and round fractions (since
$\sum_{i=1}^{n-1} x_i$ must be integral) to get the desired results.
When $n$ is even combine
\[ \left( \sum_{i=1}^{(n-2)/2} i(x_i + x_{n-i}) \right)
+ \frac{n}{2} x_{\frac{n}{2}} \geq {n \choose 2} \]
from (\ref{lb1e}) with $j=1$ and $h=n$ and
\[ \sum_{i=1}^{(n/2)-1} ix_{\frac{n}{2} - i} \geq
S\left( \frac{n}{2} \right) \]
from (\ref{rgt}) with $j = \frac{n}{2}$ and
\[ \sum_{i=1}^{(n/2)-1} ix_{\frac{n}{2} + i} \geq
S\left( \frac{n}{2} \right) \]
from (\ref{lft}) with $j = \frac{n}{2}+ 1$ to obtain
\[ \sum_{i=1}^{n-1} \frac{n}{2} x_i \geq {n \choose 2} +
2S\left( \frac{n}{2} \right) = S(n). \]
So then
\[ \sum_{i=1}^{n-1} x_i \geq \frac{2}{n}S(n). \]
We now use the bounds of Lemma \ref{ess} for $S(n)$
to get
\[ \sum_{i=1}^{n-1} x_i \geq \frac{2}{n} \left(
n^2 - n - \frac{n}{2} \left\lfloor \log_2 n \right\rfloor
\right) =
2n - 2 - \left\lfloor \log_2 n \right\rfloor
\mbox{ If $n$ is of Type I } \]
\[ \sum_{i=1}^{n-1} x_i > \frac{2}{n} \left(
n^2 - n - \frac{n}{2} \left\lfloor \log_2 n \right\rfloor
\right) =
2n - 2 - \left\lfloor \log_2 n \right\rfloor
\mbox{ If $n$ is of Type II } \]
\[ \sum_{i=1}^{n-1} x_i > \frac{2}{n} \left(
n^2 - \frac{3}{2}n - \frac{n}{2} \left\lfloor \log_2 n \right\rfloor
\right) =
2n - 3 - \left\lfloor \log_2 n \right\rfloor
\mbox{ If $n$ is of Type III. } \]
For Types II and III
since the inequality is strict and since
$\sum_{i=1}^{n-1} x_i$ must be integral we get the desired bounds.
When $n$ is odd combine
\[ \sum_{i=1}^{(n-1)/2} i(x_i + x_{n-i})
\geq {n \choose 2} \]
from (\ref{lb1o}) with $j=1$ and $h=n$ and
\[ \sum_{i=1}^{\frac{n+1}{2} -1} ix_{\frac{n+1}{2} - i} \geq
S\left( \frac{n+1}{2} \right) \]
from (\ref{rgt}) with $j = \frac{n+1}{2}$ and
\[ \sum_{i=1}^{\frac{n+1}{2}-1} ix_{\frac{n-1}{2} + i} \geq
S\left( \frac{n+1}{2} \right) \]
from (\ref{lft}) with $j = \frac{n+1}{2}$ to obtain
\[ \sum_{i=1}^{n-1} \frac{n+1}{2} x_i \geq {n \choose 2} +
2S\left( \frac{n+1}{2} \right) =
-n + {n+1 \choose 2} +2S\left( \frac{n+1}{2} \right) =
S(n+1) - n . \]
So then
\[ \sum_{i=1}^{n-1} x_i \geq \frac{2}{n+1}\left(
S(n+1) - n \right). \]
We now use the bounds of Lemma \ref{ess} for $S(n)$.
Note that when $n$ is odd and Type I then $n+1$ is Type IVe.
If $n$ is Type II then $n+1$ is Type I or II. If
$n$ is Type III and $n \not = 2^k -1$ then $n+1$ is Type III.
In each of the previous cases $\lfloor \log_2 (n+1) \rfloor =
\lfloor \log_2 n \rfloor$. If $n = 2^k -1$ then $n+1$ is Type I and
$\lfloor \log_2 (n+1) \rfloor = \lfloor \log_2 n \rfloor + 1$.
With some algebra we get
\begin{eqnarray*}
\sum_{i=1}^{n-1} x_i & \geq &
\frac{2}{n+1} \left( (n+1)^2 - (n+1) - \frac{n+1}{2} \lfloor
\log_2 (n+1) \rfloor - 1 - n \right) \\ & = &
2n - 2 - \left\lfloor \log_2 n \right\rfloor
\mbox{ If $n$ is of Type I } \\
\sum_{i=1}^{n-1} x_i & > &
\frac{2}{n+1} \left( (n+1)^2 - (n+1) - \frac{n+1}{2} \lfloor
\log_2 (n+1) \rfloor - n \right) \\ & = &
2n - 2\frac{n}{n+1} - \left\lfloor \log_2 n \right\rfloor
\mbox{ If $n$ is of Type II } \\
\sum_{i=1}^{n-1} x_i & > &
\frac{2}{n+1} \left( (n+1)^2 - \frac{3}{2}(n+1) - \frac{n+1}{2} \lfloor
\log_2 (n+1) \rfloor - n \right) \\ & = &
2n - 1 - 2\frac{n}{n+1} - \left\lfloor \log_2 n \right\rfloor
\mbox{ If $n \not = 2^k -1$ is of Type III } \\
\sum_{i=1}^{n-1} x_i & \geq &
\frac{2}{n+1} \left( (n+1)^2 - (n+1) - \frac{n+1}{2} \lfloor \log_2 (n+1)
\rfloor - n \right) \\
& = & 2n - 1 - 2 \frac{n}{n+1} - \left\lfloor \log_2 n \right\rfloor
\mbox{ If $n = 2^k - 1$ }
\end{eqnarray*}
Rounding since
$\sum_{i=1}^{n-1} x_i$ must be integral we get the desired bounds.
$\Box$
Since $s(n) \geq n + \sum_{i=1}^{n-1} x_i$ we get
\begin{cor} \label{corl}
If $n$ is Type I or III then
$s(n) \geq 3n - 2 - \lfloor \log_2 n \rfloor$. If $n$ is Type II
then
$s(n) \geq 3n - 1 - \lfloor \log_2 n \rfloor$. \end{cor}
For example, to get a bound on $s(9)$ we combine
$x_1 + 2x_2 + 3x_3 + 4x_4 + 4x_5 + 3x_6 + 2x_7 + x_8 \geq
{9 \choose 2} = 36$ from (\ref{lb1o}) with
$4x_1 + 3x_2 + 2x_3 + x_4 \geq S(5) = 15$ from (\ref{rgt})
and $x_5 + 2x_6 + 3x_7 + 4x_8 \geq S(5) = 15$ from (\ref{lft})
to obtain
$5\sum_{i=1}^8 x_i \geq 66$ or $\sum_{i=1}^{8} x_i \geq 13.2$.
Since the $x_i$ must be integral we round up to get
$\sum_{i=1}^8 x_i \geq 14$. Hence $s(9) \geq 9+ 14$.
We can in fact show that $s(9) = 23$ using the methods similar to
those in Section \ref{exv}.
\section{Exact Values} \label{exv}
In this section we construct tournaments on
$3n - 2 - \lfloor \log_2 n \rfloor$ vertices having the transitive
tournament $T_n$ as a minimum feedback arc set when
$n = 2^k - 2^t$. The details of the proof are a bit long, however,
the main ideas can be found in the description of the tables $C_n$
below.
We first do this for $n = 2^k$.
Let $\alpha(i)$ be the exponent in the highest power of 2 dividing
$i$. We will show that if $x_i = \alpha(i) + 1$ then in $T(\vec x,n)$
we can construct ${n \choose 2}$ arc disjoint $3-$cycles.
Then any minimum feedback arc set has size at least ${n \choose 2}$
and $T_n$ is a minimum feedback arc set.
Observing that
$\sum_{i=1}^{2^k-1} (\alpha(i) + 1) = 2^{k+1} - 2 - k$ then completes
the proof. For $n = 2^k - 2^t$ we simply restrict the tournament above
for $2^k$ to the first $n$ vertices of $T_{2^k}$. For other
values of $n$ similar restrictions
can be used to improve the upper bounds $s(n) \leq 3n - 4$ obtained
in [\ref{bhirt}]. However these new upper bounds are not equal to the
lower bounds of Theorem \ref{tlb} in these cases.
A convenient way to view the construction of the triangles is to use
an array $C_n$ with
entries $C_n(i,j)$ for $1 \leq i < j \leq n$ integral ordered
pairs $(a,b)$. An entry $(i,j)$ in $C_n$ will correspond to vertex
$u_{i,j}$ in $T(\vec x,n)$. The $3-$cycles will be
$(v_i, u_{c(i,j)}, v_j)$. We have the following table for $n = 4$:
\[ \begin{tabular}{l|c|c|c|}
\multicolumn{1}{c}{} & \multicolumn{1}{c}{2} & \multicolumn{1}{c}{3} &
\multicolumn{1}{c}{4} \\ \cline{2-4}
1 & 1,0 & 2,1 & 2,0 \\ \cline{2-4}
\multicolumn{2}{l|}{2} & 2,0 & 2,1 \\ \cline{3-4}
\multicolumn{3}{l|}{3} & 3,0 \\ \cline{4-4}
\end{tabular} \]
From this we get the arc disjoint $3-$cycles in $T(\vec x,n)$
$(v_1, u_{1,0}, v_2)$, $(v_1, u_{2,1}, v_3)$,
$(v_1, u_{2,0}, v_4)$, $(v_2, u_{2,0}, v_3)$,
$(v_2, u_{2,1}, v_4)$, $(v_3, u_{3,0}, v_4)$
containing the arcs of $T_4$. In this case we need $x_2 \geq 2$
since there are two pairs with first entry 2.
Similarly $x_1 \geq 1$ and $x_3 \geq 3$.
Next is the table $C_8$.
\[ \begin{tabular}{l|c|c|c|c|c|c|c|}
\multicolumn{1}{c}{} & \multicolumn{1}{c}{2} &
\multicolumn{1}{c}{3} & \multicolumn{1}{c}{4} &
\multicolumn{1}{c}{5} & \multicolumn{1}{c}{6} &
\multicolumn{1}{c}{7} & \multicolumn{1}{c}{8} \\ \cline{2-8}
1 & 1,0 & 2,1 & 2,0 & 4,2 & 3,0 & 4,1 & 4,0 \\ \cline{2-8}
\multicolumn{2}{l|}{2} & 2,0 & 2,1 & 3,0 & 4,2 & 4,0 &
4,1 \\ \cline{3-8}
\multicolumn{3}{l|}{3} & 3,0 & 4,1 & 4,0 & 4,2 & 5,0 \\ \cline{4-8}
\multicolumn{4}{l|}{4} & 4,0 & 4,1 & 5,0 & 4,2 \\ \cline{5-8}
\multicolumn{5}{l|}{5} & 5,0 & 6,1 & 6,0 \\ \cline{6-8}
\multicolumn{6}{l|}{6} & 6,0 & 6,1 \\ \cline{7-8}
\multicolumn{7}{l|}{7} & 7,0 \\ \cline{8-8}
\end{tabular} \]
The entry $C_8(2,6)=(4,2)$ gives the $3-$cycle $(v_2,u_{4,2},v_6)$.
Also, $\sum x_i = 11$ since there are 11 ordered pairs. This shows
that $s(8) \leq 11$.
In order for the $3-$cycles to be well defined we must have
\begin{equation} \label{cee1}
\mbox{ if } C_n(i,j) = (a,b) \mbox{ then } i \leq a < j. \end{equation}
In order that the arcs of the cycles be disjoint
\begin{equation} \label{cee2}
\mbox{ Each ordered pair appears at most once in each
row and in each column } \end{equation}
To construct $C_{2n}$ from $C_n$ we do the following:
The upper left triangular block is $C_n$.
The lower right triangular block is $C_n$ with $n$ added to the first
entry of each pair. For the remaining
$n$ by $n$ upper right square (rows $1,2 \ldots n$ and columns
$n+1, \ldots 2n$) start with upper right square (rows
$1,2, \ldots n/2$ and columns $n/2 + 1, \ldots n$) in $C_n$.
Replace each entry $(a,b)$ by a $2$ by $2$ square whose diagonal
elements are $(2a,b+1)$. For example the entries $(4,2)$ in positions
$C_8(1,5)$ and $C_8(2,6)$ are obtained from the entry $(2,1)$ in
position $C_4(1,3)$. The off diagonal entries in the $2$ by $2$ square
are determined by their position as described below.
More formally
\begin{equation} \label{con1}
C_{2n}(i,j) = C_n(i,j) \mbox{ if } j \leq n
\mbox{ (and hence } i < n). \end{equation}
\begin{equation} \label{con2}
C_{2n}(i,j) = C_n(i-n,j-n) + (n,0) \mbox{ if } i > n+1
\mbox{ (and hence } j > n + 1). \end{equation}
\begin{equation} \label{con3}
C_{2n}(i,j) = \left(\frac{i+j-1}{2}, 0\right) \mbox{ if }
i \leq n \mbox{ and } j > n \mbox{ and } i+j \mbox{ odd.} \end{equation}
\begin{equation} \label{con4} C_{2n}(i,j) = (2a, b+1) \mbox{ if }
i \leq n \mbox{ and } j > n \mbox{ and } i+j \mbox{ even}
\mbox{ where } C_n\left(\left\lceil \frac{i}{2} \right\rceil,
\left\lceil \frac{j}{2} \right\rceil\right) = (a,b).
\end{equation} \\
Examining the construction from the tables above reveals that
the $C_n$ satisfy (\ref{cee1}) and (\ref{cee2}) and that there are
pairs $(a,b)$ for $1 \leq a < n$ and for a given $a$, for
$0 \leq b \leq \alpha(a)$. In order to prove this
carefully, there are a number of details to check. Some extra
notation will be useful.
If an ordered pair $(a,b)$ appears exactly once in each row and each
column of the sub-array of $C_n$ in rows $r,r+1, \ldots, r+m$
and columns $s,s+1, \ldots, s+m$ then we will say that
$(a,b)$ is a {\em transversal} on $C_n[r,r+m;s,s+m]$.
\begin{lem} \label{trans}
If $(a,b)$ is a transversal on $C_n[r,r+m;s,s+m]$ with
$r \leq n/2$ and $s > n/2$ then $(2a,b+1)$ is a transversal
on $C_{2n}[2r-1,2r+2m;2s-1,2s+2m]$.
\end{lem}
Proof: The entries of the form $(2a,b+1)$ on
$C_{2n}[2r-1,2r+2m;2s-1,2s+2m]$ come from entries $(a,b)$ in
$C_n[r,r+m;s,s+m]$ using (\ref{con4}). The entries in $C_{2n}$ with
$i + j$ odd have second term $0$. So we need to show that
there is a transversal on entries with $i+j$ even.
For $2r-1 \leq 2i- 1 < 2r+2m$ and $2s-1 \leq 2j-1 < 2s+2m$,
$(2a,b+1)$ appears in $C_{2n}(2i-1,2j-1)$ if and only
if $(a,b)$ appears in $C_n(i,j)$. For
$2r-1 < 2i \leq 2r+2m$ and $2s-1 < sj \leq 2s+2m$
$(2a,b+1)$ appears in $C_{2n}(2i,2j)$ if and only
if $(a,b)$ appears in $C_n(i,j)$. Then the transversal property in
$C_n$ and (\ref{con4}) ensures the transversal property
in $C_{2n}$. $\Box$
\begin{lem} \label{cee3}
For $n = 2^k$, the following hold for $C_n$: \\
(a) $C_n(i,j) = (a,0)$ if and only if $i + j$ is odd and
$a = (i+j-1)/2$. \\
(b) For $1 \leq a < n$, if $(a,b)$ is an entry then
$0 \leq b \leq \alpha(a)$. \\
(c1) If $1 \leq a \leq n/4$ and $0 \leq b \leq \alpha(a)$
then $(a,b)$ is a transversal on $C_n[1,a;a+1,2a]$ and there are no
other $(a,b)$ entries. \\
(c2) If $3n/4 \leq a \leq n-1$ and $0 \leq b \leq \alpha(a)$
then $(a,b)$ is a transversal on $C_n[2a-n+1,a;a+1,n]$
and there are no other $(a,b)$ entries. \\
(d1) If $n/4 < a < n/2$ and $0 \leq b \leq \alpha(a)$ then
$(a,b)$ is a transversal on $C_n[1,a;a+1,2a]$. This transversal
can be decomposed into disjoint transversals on
$C_n[2a-n/2+1,a;a+1,n/2]$ and
on $C_n[1,2a-n/2;n/2+1,2a]$. There are no other
$(a,b)$ entries. \\
(d2) If $n/2 < a < 3n/2$ and $0 \leq b \leq \alpha(a)$ then
$(a,b)$ is a transversal on $C_n[2a-n+1,a;a+1,n]$. This transversal
can be decomposed into disjoint transversals on
$C_n[n/2+1,a;a+1,2a-n/2]$ and on $C_n[2a-n+1,n/2;2a-n/2+1,n]$.
There are no other $(a,b)$ entries. \\
(e) If $a = n/2$ and $0 \leq b \leq \alpha(a)$ then
$(a,b)$ is a transversal on $C_n[1,a;a+1,n]$ and
there are no other $(a,b)$ entries.
\end{lem}
Proof: We will use induction. The conditions hold for
$C_2$, which consists of the single entry $C_2(1,2) = (1,0)$.
Assume that (a), (b), (c), (d) and (e) hold for $C_n$ and consider
$C_{2n}$. We will say that $(a,b)$ is a (*) entry if
it arises from (*) in the definition of $C_{2n}$.
Entries $(a,0)$ are not created by (\ref{con4}). Using
(\ref{con3}) and inductively (\ref{con1}) and (\ref{con2}) it is
straightforward to check that (a) holds.
For $a$ odd, (b) follows immediately from (a). For $a$ even,
if $(a,b)$ is a (\ref{con1}) entry then $b \leq \alpha(a)$ by
induction. If $(a,b)$ is a (\ref{con2}) entry then
$b \leq \alpha(n-a) = \alpha(a)$ by induction and since $n = 2^k$.
If $(a,b)$ is a (\ref{con4}) entry then $b \leq \alpha(a/2)$
since it comes from $(a/2,b-1)$ in $C_n$. So
$(b+1) \leq \alpha(a)$ and (b) holds.
Using (a) (and $i < j$) it is straightforward to check (c), (d) and (e)
for pairs of the form $(a,0)$ and hence $C_{2n}(i,j)$ with $i+j$ odd.
So we assume $b \geq 1$ and $i + j$ even.
If $a$ is odd then the only pair using $a$ is $(a,0)$. So we assume
$a$ is even. Thus we will write $2a$ instead of $a$.
Case c1: If $2a \leq 2a \leq n/2$ then $(2a,b)$ does not appear
as a (\ref{con2}) entry. Also, if
$C_n(\lceil (i/2) \rceil, \lceil j/2 \rceil) =(a,b-1)$
then (c1) applies and $\lceil (j/2) \rceil \leq 2a$ hence
$j \leq 4a \leq n$. So $(2a,b)$ does not appear as a (\ref{con4})
entry. Then, $(2a,b)$ appears only as a (\ref{con1}) entry
and (c1) and (d1) inductively show that
$(2a,b)$ appears only as a transversal on
$C_n[1,a;a+1,2a]$. Since $C_{2n} = C_n$ in this region
$(2a,b)$ appears only as a transversal on
$C_{2n}[1,a;a+1,2a]$ and (c1) holds.
Case c2: Similarly, if $2a \geq 3n/2 \leq 2n-2$ then $(2a,b)$
does not appear as a (\ref{con1}) entry. Also, if
$C_n(\lceil (i/2) \rceil, \lceil j/2 \rceil) =(a,b-1)$
then (c2) applies and $\lceil (i/2) \rceil \geq 2a-n+1$ hence
$i > 4a -2n \geq n$. So $(2a,b)$ does not appear as a (\ref{con4})
entry. Then, $(2a,b)$ appears only as a (\ref{con2}) entry and
(c2) and (d2) inductively show that
$(2a-n,b)$ appears only as a transversal on
$C_n[4a-3n+1,2a-n;2a-n+1,n]$. From (\ref{con2}) we add
$n$ to the indices of each of the rows and columns to get the
appearances of $(2a,b)$ in $C_{2n}$. So $(2a,b)$ appears only as a
transversal on $C_{2n}[4a-2n+1,2a;2a+1,2n]$, which is (c2).
Case d1: If $n/2 < 2a < n$ then $(2a,b)$ appears as a (\ref{con1}) and
a (\ref{con4}) entry. When $(2a,b)$ appears as a (\ref{con1}) entry
(c2) and (d2) inductively give a transversal on
$C_n[4a-n+1,2a;2a+1,n]$. By (\ref{con1}) this gives a transversal of
$(2a,b)$ on $C_{2n}[4a-n+1,2a;2a+1,n]$. The first of the disjoint
transversal in (d1).
The (\ref{con4}) appearances of $(2a,b)$ arise from
appearances of $(a,b-1)$ in $C_n(i,j)$ with $i < n/2$ and $j > n$.
Inductively, (c1) or (d1) shows that $(a,b-1)$ is a transversal on
$C_n[1,2a-n/2;n/2+1,2a]$.
Lemma \ref{trans} then gives a $(2a,b)$ transversal on
$C_{2n}[1,4a-n;n+1,4a]$. The second disjoint transversal in (d1).
Case d2: If $n < 2a < 3n/2$ then $(2a,b)$ appears as a (\ref{con2})
and a (\ref{con4}) entry. When $(2a,b)$ appears as a (\ref{con2})
entry (c1) and (d1) inductively show that $(2a-n,b)$ is a
transversal on $C_n[1,2a-n;2a-n+1,4a-2n]$. Adding $n$ to each of
these entries for (\ref{con2}) we get a $(2a,b)$ transversal
on $C_{2n}[n+1,2a;2a+1,4a-n]$. The first disjoint transversal in (d2).
The (\ref{con4}) appearances of $(2a,b)$ arise from appearances
of $(a,b-1)$ in $C_n(i,j)$ with $i \leq n/2$ and $j > n$.
Inductively (c2) or (d2) shows that $(a,b-1)$ is a transversal on
$C_n[2a-n+1,a;a+1,n]$. Lemma \ref{trans} then gives a $(2a,b)$
transversal on $C_{2n}[4a-2n+1,2a;2a+1,2n]$. The second disjoint
transversal in (d2).
Case e:
For $2a = n$ the proof is the same as the second part of the proof of
(d1). So (e) holds. $\Box$
\begin{thm} \label{mt}
For $0 \leq t \leq k-1$,
if $n = 2^k - 2^t$ then $s(n) = 3n - 2 - \lfloor \log_2 n \rfloor$.
\end{thm}
Proof: Corollary \ref{corl} gives
$s(n) \geq 3n - 2 - \lfloor \log_2 n \rfloor$.
For $s(n) \leq 3n - 2 - \lfloor \log_2 n \rfloor$
we first consider the case
$n = 2^{k+1}-2^k = 2^k$. Construct $T(\vec x,2^k)$ with
$x_i = \alpha(i)+1$. Conditions (c), (d) and (e) of Lemma \ref{cee3}
give (\ref{cee1}) and (\ref{cee2}). Thus
$(v_i, u_{c(i,j)}, v_j)$ are arc disjoint $3-$cycles.
From the construction of $C_n$ there are ${2^k \choose 2}$ of these
cycles. So $T(\vec x,2^k)$ has $T_{2^k}$ as a minimum feedback arc set.
(Note, we need to use these cycles since we have not shown that
$\vec x$ is feasible for ILP. Our proof using $C_{2^k}$ in fact shows
this.)
Condition (b) of Lemma \ref{cee3} gives $x_i = \alpha(i) +1$.
Since $T(\vec x,2^k)$ has $n + \sum_{i=1}^{2^k-1} x_i$ vertices,
it remains to show that
$\sum_{i=1}^{2^k-1} (\alpha(i) + 1) = 2^{k+1} - 2 - k$. Observe that
for $1 \leq i < 2^k$, $\alpha(i) = \alpha(2^k - i)$. So by induction
\[ \sum_{i=1}^{2^k-1} (\alpha(i) + 1) =
2 \left(\sum_{i=1}^{2^{k-1}-1} \alpha(i) \right) + \alpha(2^{k-1})+1
= 2\left(2^k - 2 -(k-1)\right) + k = 2^{k+1} - 2 - k. \]
For $n = 2^k - 2^t$ when $0 \leq t \leq k-2$ delete
$v_1, \ldots, v_{2^t}$ and $u_{i,j}$ for $1 \leq i \leq 2^t$
from $T(\vec x,2^k)$. Then $T_n$ is a minimum feedback arc set of
the new tournament since the arc disjoint cycles from $C_{2^k}$ can
still be used. The number of deleted vertices is
\[ 2^t + \sum_{i=1}^{2^t} (\alpha(i) + 1) =
2^t + \left(2^{t+1} - 2 - t \right) + (\alpha(2^t) + 1) =
3 \cdot 2^{t} - 2 - t + (t+1) =
3 \cdot 2^t -1. \]
The number of remaining vertices is
\[ 3\cdot 2^k - 2 - k - \left(3 \cdot 2^t - 1\right) =
3\cdot\left(2^k-2^t\right) - 2 - (k-1) =
3n - 2 - \lfloor \log_2 n \rfloor. \Box \]
For other values of $n$ we can obtain upper bounds on $s(n)$ in a manner
similar to the previous proof, but these bounds will not equal the
lower bounds of Corollary \ref{corl}. If $\lfloor \log_2 n \rfloor = k$
and $t$ is such that $2^{k+1} - 2^{t+1} < n < 2^{k+1} - 2^t$ let
$m = 2^{k+1} - n$. Using the tournament for $2^{k+1} - 2^t$ from the
proof of Theorem \ref{mt} and using the lower bound for $s(m+1)$
from Corollary \ref{corl} and calculating as above we get
\[ s(n) \leq 3n - 2 - \lfloor \log_2 n \rfloor +
\left\lfloor \log_2 (2^{k+1} - 2^t - n+1 ) \right\rfloor. \]
For values of $n$ other than $2^k +1$ and
those covered by Theorem \ref{mt} this
bound is at least as good as the bound $s(n) \leq 3n - 4$
found in [\ref{bhirt}] and it is better when $m+1 < 2^{k-2}$.
\section{Conclusion} \label{adc}
There are a number of questions that remain. The proof of
Theorem \ref{mt} could be shortened by showing directly
that $x_i = \alpha(i) + 1$ satisfies ILP without resorting to
the tables $C_n$. However, using the approach of such tables
may prove useful in showing that the lower bounds give $s(n)$ in general.
As we have
noted before, we have the following conjecture \vspace{\baselineskip} \\
{\bf Conjecture} {\em If $n$ is Type I or III then
$s(n) = 3n - 2 - \lfloor \log_2 n \rfloor$ and if
$n$ is Type II then $s(n) = 3n - 1 - \lfloor \log_2 n \rfloor$.} \\
As in Section \ref{exv} this conjecture can be answered with a
positive answer to {\vspace{\baselineskip} \\
{\bf Conjecture} {\it
Let $t(n)$ denote the minimum number of ordered pairs needed to
fill a strictly upper triangular array $C_n(i,j)$
($1 \leq i < j \leq n$) such that the pairs in each row are distinct,
the pairs in each column are distinct and if
$C_n(i,j) = (a,b)$ then $i \leq a < j$. If $n$ is Type I or III then
$t(n) = 3n - 2 - \lfloor \log_2 n \rfloor$ and if
$n$ is Type II then $t(n) = 3n - 1 - \lfloor \log_2 n \rfloor$.} \\
If the conjecture below is true then these first two conjectures are
equivalent.
In a digraph the number of arc disjoint cycles is
at most the minimum size of a feedback arc set. All of our proofs
have used tournaments in which equality holds. In general, even for
tournaments, the minimum size of a feedback arc set may be strictly
larger than the maximum number of arc disjoint cycles.
In fact, for large $m$ a random tournament on $m$ vertices has
minimum size of a feedback arc set
$\frac{1}{2}{m \choose 2} - cm^{3/2}$ with probability approaching
one [\ref{vega}] while it has at most $
\lfloor m/3 \lfloor (m-1)/2 \rfloor \rfloor \leq
\frac{1}{3}{m \choose 2}$ arc disjoint cycles (since each cycle
has at least three arcs) [\ref{cgh}]. When the host graph is not
a tournament, but a planar digraph, then the Luchesi-Younger Theorem
[\ref{ly}] shows that equality does hold. For feedback {\em vertex}
sets, [\ref{srt}] establishes that for any finite digraph with
$s$ (vertex-) disjoint circuits, there exists a feedback vertex
set of size at most some function $f(s)$.
See the survey [\ref{bt}] for
related work. However, if a tournament has a minimum feedback arc
set whose arcs form an acyclic tournament on $n$ vertices
then it must be of the form $T(\vec x,n)$ for $\vec x$ satisfying ILP.
The conditions for ILP lead us to the following conjecture
mentioned in the introduction: \vspace{\baselineskip} \\
{\bf Conjecture} {\it If $T$ is a tournament with a minimum feedback arc set
a set of arcs which form a (smaller) acyclic tournament
then the maximum number of arc disjoint cycles in $T$
equals the minimum size of a feedback arc set. } \\
If $D$ is any digraph containing a Hamiltonian path, a similar table
to the $C_n$ in Section \ref{exv}
can be constructed (with blocks corresponding to missing arcs in
$D$ left blank) to get tournaments with $D$ as a minimum feedback arc set.
Any tournament with $D$ as a minimum feedback arc set will have
a structure similar to $T(\vec x,n)$; it is completely determined
by the sizes $x_i$. Then,
lower bounds on the smallest size of such a tournament can be
obtained by the analogue of ILP with the right hand sides of the
inequalities replaced with the number of arcs of $D$ in the segment.
We do not know if this ILP gives the exact value of the size of the
tournament. It may be possible that analogues of the questions above
hold in this case. For example it is not hard to show that if
$T$ has a feedback arc set whose arcs are the arcs of a (Hamiltonian)
path then the minimum size of a feedback arc set in $T$ equals the
maximum number of arc disjoint cycles. \vspace{\baselineskip} \\
{\bf Question:} {\em If $T$ is a tournament with a minimum feedback arc
set a set of arcs which form an acyclic digraph with a Hamiltonian path
is it true that the maximum number of arc disjoint cycles in $T$
is equal to the minimum size of a feedback arc set?
Given a digraph $D$ which contains a Hamiltonian path,
is it possible to efficiently compute the size of a smallest tournament
with a minimum feedback arc set whose arcs are the arcs of $D$?}
Acknowledgement: The author would like to thank a referee for bringing
[\ref{srt}] to his attention.
\section*{References}
\begin{enumerate}
\item \label{bhirt}
J.P.\ Barthelemy, O.\ Hudry, G.\ Isaak, F.S.\ Roberts and
B.\ Tesman, The Reversing Number of a Digraph,
Discrete Applied Mathematics {\bf } to appear (1995)
\item \label{bt}
J.C.\ Bermond and C.\ Thomassen, Cycles in Digraphs -- a Survey,
J.\ Graph Theory {\bf 5} (1981), 1--43.
\item \label{cgh}
G.\ Chartrand, D.\ Geller and S.\ Hedetniemi,
Graphs with Forbidden Subgraphs, J.\ Combinatorial Theory B, {\bf 10}
(1971) 12--41.
\item \label{gu}
W.\ Gu, K.B.\ Reid and W.\ Schnyder, Realization of Digraphs
by Preferences Based on Distances in Graphs, J.\ Graph Theory,
{\bf 19} (1995) 367--373.
\item \label{glenn}
G.\ Hurlbert, personal communication.
\item \label{it}
G.\ Isaak and B. Tesman, The Weighted Reversing Number of a Digraph,
Congressus Numerantium, {\bf 83} (1991) 115--124.
\item \label{jung}
M.\ J\"{u}nger, {\em Polyhedral Combinatorics and the Acyclic
Subdigraph problem}, Heldermann Verlag, Berlin, 1985.
\item \label{ly}
C.L.\ Lucchesi and D.H.\ Younger, A Minimax Theorem for
Directed Graphs, J.\ London Math.\ Soc.\ (2), {\bf 17}
(1978) 369-374.
\item \label{srt} P.D.\ Seymour, G.N.\ Robertson and R.\ Thomas,
unpublished
\item \label{vega}
W.\ F.\ de la Vega,
On the Maximum Cardinality of a Consistent Set of Arcs in a Random
Tournament, J.\ Combinatorial Theory B {\bf 35} (1983) 328--332.
\item \label{yg} D.H. Younger, Minimum feedback arc sets for a directed
graph, IEEE Transactions, {\bf CT-10} (1963), No. 2, 240-245.
\end{enumerate}
\end{document}