1
$\begingroup$

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!

  • 1
    Thanks :D That was the key step I needed. Man, these questions look so simple once you've solved them.2011-10-13

1 Answers 1

3

You don’t need a probabilistic argument, but induction on $k$ will work. Don’t make an arbitrary split of your $2^{k+1}$ vertices. Instead, pick any vertex $v$, let $L = \{u:u\to v\},$ and let $R=\{u:v\to u\}.$ (By $u\to v$ I mean that there is an edge from $u$ to $v$.) $|L|+|R| = 2^{k+1}-1$, so one of $L$ and $R$ contains at least $2^k$ points. Now apply your induction hypothesis to that set, and you should find it easy to fit $v$ in to the resulting transitive $k$-tournament.

  • 0
    Thank you, that was very clear :)2011-10-13