So I am having a hard time with this problem:
A transitive tournament is a tournament for which the vertices can be numbered in such a way that (i, j) is an edge if and only if i < j. Show that if $k \leq \log_{2}n$, every tournament on $n$ vertices has a transitive subtournament on $k$ vertices. (A Course in Combinatorics, Second Edition)
What I have tried so far: First I tried induction. (WLOG assume $n = 2^k$ and induct on $k$.) I split $2^{k+1}$ into two groups of $2^k$ vertices. One group is guaranteed to have a tournament on $k-1$ vertices. So we just have to find a vertex in the other group that "fits inside" the tournament properly. Modeling the subtournament as a chain, we just need to find a vertex that "fits inside" the chain, i.e. you can take the chain union that vertex and still get a chain.
I do not know how to prove such a vertex exists, though. I was trying to use the "probabilistic method" that was discussed in the chapter, but I still don't understand it properly. I guess we have to show that some probability is greater than 0, like the probability of finding a vertex that "fits inside" the chain given a random assignment of each of the $2^k$ vertices to a comparison with the other group, but I'm still confused about what probability we're trying to find and why it's helpful at all. Also, I have no idea if I'm on the right track.
Can you give me a hint as to how to solve this problem?
Thanks!