Minimum number of transitive paths in tournament

Question

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.

Answer 1

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.$$

Answer 2

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).