Author: José de Jesús García Ruvalcaba
Date: 05:23:00 06/09/04
Go up one level in this thread
On June 09, 2004 at 07:01:00, José de Jesús García Ruvalcaba wrote: >Let me generalise the problem, we have a 3-regular simple graph (simple means no >loops and no parallel arcs, and 3-regular implies also that the number of >vertices is even and at least four), lets find a pairing. >I have not studied graph theory in a long time, but since the concept of regular >graph is quite common and pairing problems are classical, I expect this problem >to be already solved. >I somewhat suspect that under those conditions there is always a pairing, just >give me some time to check a few books. >José. Confirmed. See "Théorie des graphes et ses applications" by Claude Berge (Dunod, Paris 1958), p. 180, chapite 18 (sorry, did not found any German edition) Théorème 7. Si un graphe connexe homogène de degré impair h=2k+1 ne contient pas d´ensemble S « X avec |U(S)| < 2k, il existe un couplage parfait utilisant une arête arbitrairement donée (I had to change the notation at two points, since I do not know how to type a few things) Anyway, taking k=1 and applying the theorem to the connected components, it implies that every simple 3-regular graph has a perfect coupling, which is what we need. The theorem says even more: you can arbitrarily select one arc of the graph and there is a pairing containing this arc. It actually implies that for any number of players, we can find swiss pairings up to n-3 rounds (you may assume n is even, if n is odd it is sharper and up to n-2 rounds). Of course I am assuming no dropouts from the tournament and other irregularities. As you have shown, it can not be in general extended to n-2 rounds (here I think only of even n, since the bye can not be given twice to the same player), you just need to create an odd cycle in the graph I defined, which is not difficult. So do not worry, as long as participants do not drop out (or are expelled like List the last time), it is posible to make 11 swiss rounds with 14 players. José.
This page took 0.01 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.