Author: Dieter Buerssner
Date: 12:55:37 07/13/04
Go up one level in this thread
On July 11, 2004 at 14:54:13, José de Jesús García Ruvalcaba wrote: >I assume you remember or found my post, there is a reference there which should >be easy to find in a big university library. The search engine is not working at the moment. >What I state is: every 3-regular graph has a perfect coupling (3-regular means >that each vertex has exactly 3 neighbours) >This implies that, once you have found pairings for the first n-4 rounds, you >can also find them for round n-3. >It does not imply that you can find the earlier pairings. I don't understand much of graphs, and don't understand the above (for example, I don't see how the pairing problem translates to a graph. I see it for one round, but for all rounds? Ther must be different kind of vertices for each round?) But it seems (=my guess) that above statement can be more generalized. It is clear, that when you have paired n-2 rounds, you can also pair round n-1 (the last round to get full round robin). It is also clear, that in general, you cannot pair rounds n-2, n-4, n-6 (easily proven by a counter example). So my guess: You can always pair rounds n-(2m-1), m=1,2,3,... when round n-(2m-2) was paired. For n mod 4 = 2 (n=6, 10, 14, 18), it is clear, that one can not always pair round n/2+1. This can easily be seen by constructing a counter example. n/2 is odd. Construct 2 groups of players. In the first n/2 rounds always one of group 1 plays vs one of group 2. So after n/2 rounds each player of group 1 has played vs. each player of group 2 and vice versa. Now it is impossible to pair round n/2+1, because here only games inside the 2 groups are possible. And because the number in each group is odd, its impossible. I think, this is the worst case, and you can always find pairings for the first n/2 rounds. For n mod 4 = 0 (n=4, 8, 12, 16, ...) I suspect one can always pair upto round n/2+1, but not anymore n/2+2. BTW. I did a Monte Carlo test with n=14 and 11 rounds (the WCCC conditions). Just pairing each round at random. Probablity, that you cannot pair round 10 is extremely low - around 4e-5% in my simulation. Probability that you cannot pair round 8 is even much lower. For round 12 it would be 30%. OTOH, for n=6, probability that you cannot pair round 4 is 25%. Regards, Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.