A tournament of order $N$ is a directed graph on $[N]$ obtained by assigning a direction to each edge of $K_{N}$. A tournament $D$ is transitive if for every triple $a, b, c \in N$, $(a, b),(b, c) \in E(D)$ implies that $(a, c) \in E(D)$. For $n \in \mathbb{N}$ let $f(n)$ be the maximum integer such that there exists a tournament of order $f(n)$ without a transitive sub-tournament of size $n$. Show that $f(n) > (1+o(1))2^{\frac{n-1}{2}}$.
The following is my attempt :
Claim 2: $f(n) > (1 + o(1))2^{\frac{n-1}{2}}$
Proof: Consider the directed graphs on the vertex set $[n]$. A permutation $\sigma$ of $[n]$ gives an unique sequence $\sigma(1) \to \sigma(2) \to \dots \to \sigma(n)$, which corresponds to a directed Hamiltonian path on $K_n$. Hence, by claim 1 (proof omitted), there exists $n!$ transitive tournaments on the underlying graph $K_n$.
Let $T$ be a random tournament on $[N]$, with $N > n$. Let $X$ be the random variable counting the number of transitive tournaments of size $n$ in $T$. By linearity of expectation and the analysis above, we have: $$\mathbb{E}[X] = n! {N \choose n} 2^{- {n \choose 2}}$$ To show the inequality in the claim, we want to find $N$ such that $\mathbb{E}[X] < 1$. Thus we have the following approximation: \begin{align*} &\ n! {N \choose n} 2^{- {n \choose 2}} = \frac{N!}{(N - n)!2^{\frac{n(n-1)}{2}}} = \left( (1 + o(1))\frac{N}{2^{\frac{n-1}{2}}} \right)^n < 1 \\ &\Rightarrow (1 +o(1))\frac{N}{2^{\frac{n-1}{2}}} < 1 \\ &\Rightarrow N < (1 + o(1))2^\frac{n-1}{2} \\ \end{align*}
I thought I would get something like $N > (1 + o(1))2^{\frac{n-1}{2}}$, and since $f(n)$ is the maximum of those $N$’s with the required property, I’d get $f(n) > N > (1 + o(1))2^{\frac{n-1}{2}}$. Where did I go wrong with my arguments?
At first I thought that if $N < (1 + o(1))2^\frac{n-1}{2}$ $(\ast)$, then this implies there exists a tournament of order $N$ without a transitive subtournament of order $n$, and so $f(n) > (1 + o(1))2^\frac{n-1}{2}$. But then, say we make the RHS of $(\ast)$ very large, then the inequality still holds, but surely $f(n)$ can’t be arbitrarily large?
Your proof is nearly correct. By rearranging the last part, the work shows that if $N\le g(n):=(1-o(1))2^{(n-1)/2}$, then there exists a tournament on $N$ vertices lacking copies of the transitive tournament of order $n$. Hence $f(n)\ge g(n)$ and the desired result follows.
Concretely I think you went wrong when writing out your implication arrows about the size of $N$, which confused the order of quantifiers.
Edit: The correct way to order the last part of your argument is as follows. Let $g(n)$ be the largest $N$ such that $\Bbb{E}[X]=n!\binom{N}{n}2^{-\binom{n}{2}} < 1$. Clearly $f(n)\ge g(n)$. By essentially the same asymptotic analysis as what you gave (since the approximation is sharp), we see that $g(n) \ge (1-o(1))2^{(n-1)/2}$. Hence, we have have that $f(n)\ge g(n) \ge (1-o(1))2^{(n-1)/2}$.
But you instead proved an upper bound for $g(n)$. Namely, your current analysis shows that if $\Bbb{E}[X]<1$ then it is necessary for $N$ to be smaller than the RHS. Thus increasing the RHS does lead to a better lower bound for $f(n)$, but rather a weaker upper bound of $g(n)$.