Problem of the Week 1067

Tournament Time

True or False: Every tournament on 7 teams has a subtournament on 4 teams that is totally ordered.

Background: A classic induction exercise proves that every tournament on 8 teams has a subtournament of size 4 that is fully ordered. This means that if 8 teams have a tournament in which each team plays each other team once (no draws), there are four teams A, B, C, D so that A beat B, C, and D, B beat C and D, and C beat D. So the question is whether the assertion is true if 8 is lowered to 7. A more standard term for "fully ordered" is "transitive."

Of course, one can ask more generally: Given m, what is the least n such that an n-tournament has a fully ordered subtournament of size m? This problem is not solved in general.

© Copyright 2006 Stan Wagon. Reproduced with permission.