Posted by: yanzhang | October 14, 2010

A Few Questions on Lazy Tournament Combinatorics

We mathematicians love those rare moments when mathematically actually appear, no matter how tenuously, in real life; they give us a great excuse to think that what we do means something. Whether that is true or not is obviously mathematician-dependent; regardless, there was some cute math here, so I would like to share it with you.

At the Guo Juan Go workshop, a group of 6 players had to play 4 games each against members of the other group. After the members matched up the first two games haphazardly, they realized that there was the possibility that they can be “stuck” if they didn’t plan out the rest of the matches, because maybe a player would have to wait (here, we make the passable assumption that in each time interval, all the players play in parallel and finish at the same time); so we sat and wondered how to design the rest of this “almost round-robin” tournament, or if we even had to (can we just keep playing haphazardly and still get all the games played?). This inspired me to think about the following problems:

1) Suppose we had 2n players who wanted to play each other exactly once, and each game takes 1 time unit. This is obviously n(2n-1) games, so the theoretical minimum blocks of time we can use would be (2n-1). Is this possible?

This looks like one of those things that we can probably do if given more time – but I’ve actually been very busy recently so I’ll be lazy and ask the readers instead. The only thing that remotely stops this problem from being trivial (assuming that it is true) is that the naive method I can think of only works for prime n: just put the players on a circle, and on time k everyone plays with the person k steps in front of him/her. However, for composite n this stops working when we hit a factor.

2) Suppose that Yan is a lazy tournament director, and he goes to the tournament late from oversleeping. Under these very reasonable assumptions, the best strategy the players have (besides plotting revenge) is to play each other haphazardly every time interval. What is the maximal number of games they can guarantee if Yan comes in k units late (related question: how late can Yan sleep but still guarantee everyone plays everyone in the minimal amount of time? Note this question only makes sense if the answer to question 1 is “Yes,” which I’m leaning towards).

I kind of like this question – obviously Yan can sleep for 1 unit of time without bothering everyone – the situation is completely symmetric no matter which of the perfect matchings of the players we use in that time period. I’ve realized that for our small case n = 3, the first 2 time intervals are also completely symmetric (the union of the two perfect matchings form a cycle in K_6), so Yan can sleep a little longer. The problem is that if Yan sleeps for 3 time intervals it *is* possible for a player to have to sit out the next time interval — we can be left with two 3-cycles in the graph of games remaining to be played.

A relevant theorem may be (although I’ve forgotten where I saw this I know it has to be true): if our graph is regular of degree at least half the number of vertices, then there is a perfect matching (note this means the players will always be able to play at least n-1 games haphazardly). I think the theorem is sharp, but it has no other assumptions so maybe we can exploit the structure on our graph. Tutte’s Theorem is also probably relevant — though I don’t know precisely how to use it right now.

3) What is the running time of the best algorithm to set up the matchings given that Yan walks in at time k?

The story ends happily for our particular case of n = 3. As I mentioned the first two time periods don’t disturb anything, so I was able to extend the tournament to get an entire round-robin and just cut off one round to have a 4-interval tournament. But in general, how fast can I do this?

4) What about for 2n-1 players? What’s the best they can do?

At a glance I think this reduces to the case of 2n by adding a mysterious player aptly-named “Bye.” Correct me if this doesn’t work.

-Yan

Advertisements

Responses

  1. 1) Suppose we had 2n players who wanted to play each other exactly once, and each game takes 1 time unit. This is obviously n(n-1) games, so the theoretical minimum blocks of time we can use would be (n-1). Is this possible?

    Either there is something that I don’t get, or this should be n(2n-1). Also, it is well-known that this can be done in 2n-1 time and there is a very simple construction.

  2. @domotorp: you’re right. I fixed the oversight.

    Yeah I suspected this would be true. However, I’ve been quite busy lately so I kinda threw this post out there to ask for this “simple” construction =) can you enlighten me a bit more?

  3. Well, any chess tournament is organized following this rule, if I know it well. My hint is that there is a very nice geometric construction. For odd n, take a perfect n-gon and then…


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: