Author: Robert Hyatt
Date: 08:23:11 06/09/04
Go up one level in this thread
On June 09, 2004 at 08:31:21, Peter Berger wrote: >On June 09, 2004 at 08:23:00, José de Jesús García Ruvalcaba wrote: > >>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é. > >I enjoyed reading your posts but you generalized the problem too much IMHO. I >specifically referred to legal Swiss pairings only. I agree that there will >always be some way of pairing left but not one that also follows the much >stricter rules for Swiss pairings. > >If you have sufficient time you can look them up here: >http://www.fide.com/official/handbook.asp?level=C04 > >Peter The _real_ problem with this is that 11 rounds, 13 players, means that 1/2 way thru the event, the top programs have played each other. The rest of the event is just burning CPU cycles, burning operator time, and providing no drama or interest for the last half of the event. Yes there can be an "upset" with a weaker program. But who really cares? Should interest in the last half of the unnecessary rounds be dependent on the hope of an upset? I don't understand why the ICGA doesn't understand this. They understood it well many years ago. What has changed??? It seems that the interest in dragging the event out to 9 days far outweighs the logistics of actually having people participate, getting machine time, etc... 13 participants is a _very_ small pool. Wonder what they would have done had they only had 10? No doubt they would have continued with the 11 round stuff. :) If the event stays this long, in another couple of years it will be an 11 round match between two players... Time to listen to the people participating...
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.