Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic

Question

So a tournament is just a complete directed graph, I believe.

I'm having trouble proving this problem. I know it is induction however. I was thinking the base case is $2^1$ vertices, and therefore we have a sub-tournament of 1 + 1 vertices, which holds.

Then in our induction step we have to show $2^{n + 1}$. But I'm not sure how to approach this. Any ideas would be extremely appreciated.

Answer 1

A tournament is a loop-free directed graph $G=(V,E)$ in which, for each pair of distinct vertices $u,v \in V$, exactly one of $(u,v)$ and $(v,u)$ is in $E$.

The proof of your claim is by induction.

For $n=0$ the claim is true since a tournament $G$ with $2^0=1$ vertices is trivially acyclic, and its only sub-tournament with $0+1=1$ vertices is $G$ itself.

Assume now that the claim holds up to some $n \ge 0$ and consider a tournament $G=(V,E)$ with $|V|=2^{n+1}$. Pick an arbitrary vertex $v \in V$, and partition the vertices of $V \setminus \{ v \}$ into two sets $L = \{ u \in V \setminus \{ v \} \mid (u,v) \in E \}$ and $ R =\{ u \in V \setminus \{ v \} \mid (v,u) \in E \}$. One of $L$ and $R$ must contain at least $\left\lceil \frac{|V \setminus \{v\}|}{2} \right\rceil = \left\lceil \frac{2^{n+1} - 1}{2} \right\rceil=2^n$ vertices. Arbitrarily select $2^n$ vertices from this set, and call the set of the selected vertices $S$. By inductive hypothesis $S$ contains an acyclic sub-tournament $S'$ of size $n+1$, and since either $S' \subseteq S \subseteq L$ or $S' \subseteq S \subseteq R$, we have that $S' \cup \{v \}$ is also acyclic. This proves the claim since $|S' \cup \{v \}| = |S'| + 1 = n+2$.