1
$\begingroup$

Show that there exists a tournament on $n$ vertices that does not contain a transitive tournament on $2\log_2n+2$ vertices.


My attempt: The number of tournaments of $n$ vertices is $2^{\binom{n}{2}}$. On the other hand, the number of tournaments that have a subtournament of $k$ vertices is at least (if I'm not mistaken) $k!\binom{n}{k}$, since The number of tournaments of size $k$ is $k!$, and there are $\binom{n}{k}$ subsets of size $k$. I thought about proving that the inequality: $$k!\binom{n}{k}\leq 2^{\binom{n}{2}}$$ holds for $k=2\log_2n+2$. Do I have a mistake somewhere? If not, I would like some help proving the above inequality.

$\endgroup$
2
$\begingroup$

To put an upper bound on the number of $n$-vertex tournaments that have a transitive subtournament on $k$ vertices, it's not enough to write $k! \binom nk$, we need to take $$k! \binom nk \color{red}{2^{\binom n2 - \binom k2}}.$$ The factor you're not accounting for is the number of ways to choose the edges outside the transitive subtournament.

Once you've done that, yes, you can continue by verifying $$ k! \binom nk 2^{\binom n2 - \binom k2} < 2^{\binom n2} $$ for $k = 2\log_2n + 2$. The idea is that if this inequality holds, then the number of $n$-vertex tournaments with a transitive subtournament on $k$ vertices is smaller than the total number of tournaments, so there is a tournament with no such transitive subtournament.

Simplifying, we want to check that $n(n-1)(n-2) \dotsm (n-k+1) < 2^{\binom k2}$; it is easier to check that $n^k < 2^{\binom k2}$, which is equivalent to $k > 2\log_2 n + 1$.


Another approach that leads to the same inequality is to consider a tournament on $n$ vertices chosen uniformly at random. Then the quantity $$ k! \binom nk 2^{-\binom k2} $$ represents the expected number of $k$-vertex transitive subtournaments, and if we show that for $k = 2\log_2 n + 2$ the expected number is less than $1$, then there must be some outcomes where the number of $k$-vertex transitive subtournaments is $0$.

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