TOURNAMENTS, BOXES AND NON-TRANSITIVE DICE
Many gymnasts compete in 2k-1 events, and are ranked in each with no ties. One competitor is deemed to have "beaten" another if she outscores the other in a majority of the events.
Afterward the organizers are embarrassed to discover that no matter how they award the prizes, there will always be a gymnast who didn't get a prize but beat every gymnast who did.
How many prizes should the organizers have had on hand to be sure this wouldn't happen?
(A meandering blackboard presentation based on recent work with N.Alon, G.Brightwell, H.Kierstead, and A.Kostochka.)
During this lecture he presented this gem, due to Imre Bárány and Jenö Lehel:
There exists a constant c = c(d) such that for any compact set S contained in Rd, there exists a subset A of S of size at most c such that S is contained in the union of "boxes" of pairs of points of A, where the box containing two points p and q is defined the smallest orthogonal box containing p and q.
A lower bound on c is doubly exponential in d (for d = 2, 4 points suffice).
Peter Winkler's talks are always beautiful this way; they start with a simple puzzle - something you could describe in a line or so - and then as the talk progresses, you realize the deeper and deeper levels of mathematics that are being used to solve the problem.
No comments:
Post a Comment