# Showing existance of tournament without transitive subtournament

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.

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