4
$\begingroup$

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if there exists an edge from $A_i$ to $A_j$ for all $i<j$. The number of transitive paths in $T$ is the sum of the number of transitive paths of each size.

What is the minimum possible number of transitive paths in a tournament $T$ with $n$ vertices?

Any approximations, references, etc. would be appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ Is "transitive path" standard notation? I think "transitive subtournament" would be more natural. $\endgroup$ – Douglas Zare Aug 26 '14 at 9:13
  • $\begingroup$ Give your vertices an order and color each edge blue if it goes from bigger to smaller and red otherwise. Each monochromatic subgraph is a transitive tournament. This gives a lower bound for $T$, if you can work out bounds for monochromatic subgraphs. Also, there is the silly upper bound where every edge is blue and $T$ is just the number of subgraphs. $\endgroup$ – Joonas Ilmavirta Aug 26 '14 at 9:46
7
$\begingroup$

As pointed out in the comments, the established name for what you call a transitive path is "transitive subtournament". Call a transitive subtournament "maximal" if it isn't included in a larger transitive subtournament. This paper contains exponential upper and lower bounds on the maximum number $M_n$ of maximal transitive subtournaments that a tournament on $n$ vertices can have. Namely, there is a constant $1.4757 \le \theta \le 1.717$ such that $$M_n = (\theta+o(1))^n.$$

$\endgroup$
2
  • $\begingroup$ Could you explain how this gives bounds for the minimum number of transitive subtournaments? $\endgroup$ – François G. Dorais Aug 30 '14 at 13:07
  • 2
    $\begingroup$ @François: As far as I'm aware, it doesn't. It's just a lead to follow. $\endgroup$ – Brendan McKay Aug 30 '14 at 13:40
2
$\begingroup$

In the 1960's, Erdos and Moser showed that there is a tournament on $n$ vertices with no transitive subtournament on $2 \log_2n$ vertices. Conversely, you can show inductively that every tournament on $n$ vertices contains a transitive subtournament on $\log_2 n$ vertices (the Erdos/Moser paper linked above attributes this result to Stearns, though I'm not sure if the linked proof is originally due to him). I think actually both of these arguments also give asymptotic bounds for your problem.

For an Upper Bound: Consider a random tournament on $n$ vertices where each edge is independently given each possible orientation with probability $1/2$. For a given $k$, the expected number of transitive subtournaments of size $k$ is $$\binom{n}{k} k! 2^{-\binom{k}{2}} \leq n^k 2^{-\binom{k}{2}}.$$ The RHS is maximized for $k=\log_2 n$, and drops off sharply on either side. So when you add up over all $k$, you get that the expected total number of transitive subtournaments is $$O\left(n^{\log_2 n}2^{-\binom{\log_2 n}{2}} \right)=O\left(n^{\frac{1}{2} \log_2 n + \frac{1}{2}} \right)$$

For a Lower Bound: Let $v_0$ be an arbitrary vertex. Then for each $i$ from $1$ to $\log_2 n-1$:

  • Divide all vertices into two classes based on whether they have an edge pointing towards or away from $v_{i-1}$.
  • Delete all vertices in the smaller class, and choose $v_{i}$ arbitrarily from the larger class.

At each step there's at least $n 2^{-i}$ choices for $v_i$, so you can generate at least $$n \frac{n}{2} \frac{n}{4} \dots \frac{n}{2^{\log_2 n-1}} = n^{\log_2 n} 2^{-\binom{\log_2 n}{2}}$$ sequences by this method. Each sequence corresponds to a transitive subtournament on $\log_2 n$ vertices, and each tournament appears at most $2^{\log_2 n}=n$ times among the sequences (The last vertex chosen must be either first or last ranked in the subtournament, the second to last vertex must be either first or last among the remaining vertices, etc.). So each tournament must contain at least $$\frac{n^{\log_2 n} 2^{-\binom{\log_2 n}{2}}}{n}$$ transitive subtournaments of size $\log_2 n$.

The latter argument is somewhat wasteful in completely ignoring the smaller half each time, and it should be possible to tighten it up to match the upper bound within a constant factor (by not throwing away the smaller set you should gain a factor of about $2$ in each of the $\log_2 n$ steps).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.