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