Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
Here's a hint: given a vertex $x$ there's a large set such that either everything in the set points to $x$, or $x$ points to everything in the set. –  user83827 Oct 13 '11 at 1:33
1  
Thanks :D That was the key step I needed. Man, these questions look so simple once you've solved them. –  badatmath Oct 13 '11 at 3:42

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you, that was very clear :) –  badatmath Oct 13 '11 at 3:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.