Life In 19x19
http://www.lifein19x19.com/

How many different pairing plans there are in round robin?
http://www.lifein19x19.com/viewtopic.php?f=45&t=11362		 Page 1 of 1
Author:  Matti [ Wed Jan 14, 2015 5:07 am ]
Post subject:  How many different pairing plans there are in round robin?
Let's call that a pairing plan is a round robin table from which you get the actual pairing by substituting the place holders with player names or identifiers. For example a four player pairing plan looks:
    1-2 3-4
    1-3 2-4
    1-4 2-3
This is the only pairing plan for four players. There is also only pairing plan for six player round robin. How many different pairing plans there are for eight player round robin? There is at least three:
one where you line up the board in one table and players rotate around the table one place each round except one player who keeps his place.

Then one may split the players in two four player groups and use four player plan within the groups. There is at least two ways to arrange the games between the groups. Can one find more?
Author:  HermanHiddema [ Wed Jan 14, 2015 8:04 am ]
Post subject:  Re: How many different pairing plans there are in round robi
How do you define when a pairing is different? There are several options I can think of.

First, some definitions:

1. In pairing theory, a single round pairing is equivalent to a perfect matching on a complete graph (adding BYE as a vertex to a graph with an odd number of vertices for convenience).

2. A round-robin tournament is a list of such perfect matchings where all edges are covered by exactly one matching (i.e. no two matchings share any edge in the graph)

One could define a unique pairing plan as a unique list of matchings. That means a pairing is different if any two games that happen in the same round in one of them do not happen in the same round in the other, and is also different if the same set of games happen in a different round.

Under that definition, you can pair four players in 6 ways.

Another definition could be that a unique pairing is a unique set of matchings. That means a pairing is different if any two games that happen in the same round in one of them do not happen in the same round in the other, but is not different if the same sets of games are played but happen in different rounds.

Under this definition, there is only one way to pair four players (as the order of the rounds does not matter).

For six players, however, one can start with 1-2, 3-4, 5-6 or with 1-2, 3-5, 4-6 or with 1-2, 3-6, 4-5 and you have different games in different rounds.

Given that you feel there is only one way to pair six players, this is also, apparently not the uniqueness constraint you are looking for.

One could further call pairings the same if they are isomorphic (this may not be the entirely correct term). If there is some way in which we can switch vertex labels (but not edges) so that the graphs become the same. This may be the definition you are looking for? I am having a hard time visualizing it, but it feels like this may indeed give several different options for 8 players, while having only one for 6 players.
Author:  Matti [ Thu Jan 15, 2015 4:08 am ]
Post subject:  Re: How many different pairing plans there are in round robi
HermanHiddema wrote:

Given that you feel there is only one way to pair six players, this is also, apparently not the uniqueness constraint you are looking for.

One could further call pairings the same if they are isomorphic (this may not be the entirely correct term). If there is some way in which we can switch vertex labels (but not edges) so that the graphs become the same. This may be the definition you are looking for? I am having a hard time visualizing it, but it feels like this may indeed give several different options for 8 players, while having only one for 6 players.


This seem to be the thing I am looking for. Pairings which can be produced from another pairing by permuting the players or the rounds belong to the same pairing plan. Or is it better to say pairing scheme?

With 8 players one can visualize the thing by putting the players in the vertexes of a cube. Let's label them 111, 112, 121, 122, 211, 212, 221, 222. An unique plan is to pair there rounds where opponents differ by numbers only in one position. then another three rounds where opponents differ by number in two positions and one more round where opponents differ by number in all positions. This pairing has an interesting property: If one chooses any two round, there exists a third round which completes two sets of four player round robins.
Author:  ez4u [ Thu Jan 15, 2015 5:02 am ]
Post subject:  Re: How many different pairing plans there are in round robi
Matti wrote:
HermanHiddema wrote:

Given that you feel there is only one way to pair six players, this is also, apparently not the uniqueness constraint you are looking for.

One could further call pairings the same if they are isomorphic (this may not be the entirely correct term). If there is some way in which we can switch vertex labels (but not edges) so that the graphs become the same. This may be the definition you are looking for? I am having a hard time visualizing it, but it feels like this may indeed give several different options for 8 players, while having only one for 6 players.


This seem to be the thing I am looking for. Pairings which can be produced from another pairing by permuting the players or the rounds belong to the same pairing plan. Or is it better to say pairing scheme?

With 8 players one can visualize the thing by putting the players in the vertexes of a cube. Let's label them 111, 112, 121, 122, 211, 212, 221, 222. An unique plan is to pair there rounds where opponents differ by numbers only in one position. then another three rounds where opponents differ by number in two positions and one more round where opponents differ by number in all positions. This pairing has an interesting property: If one chooses any two round, there exists a third round which completes two sets of four player round robins.

Maybe I misunderstand this but why not skip the cube, label them 000,001,010,... and accept that you are just counting in binary? :scratch:
Author:  Matti [ Fri Jan 16, 2015 2:58 am ]
Post subject:  Re: How many different pairing plans there are in round robi
ez4u wrote:
Matti wrote:
This seem to be the thing I am looking for. Pairings which can be produced from another pairing by permuting the players or the rounds belong to the same pairing plan. Or is it better to say pairing scheme?

With 8 players one can visualize the thing by putting the players in the vertexes of a cube. Let's label them 111, 112, 121, 122, 211, 212, 221, 222. An unique plan is to pair there rounds where opponents differ by numbers only in one position. then another three rounds where opponents differ by number in two positions and one more round where opponents differ by number in all positions. This pairing has an interesting property: If one chooses any two round, there exists a third round which completes two sets of four player round robins.

Maybe I misunderstand this but why not skip the cube, label them 000,001,010,... and accept that you are just counting in binary? :scratch:

That is possible too. I just used the cube for visualizing.
Author:  zorq [ Sun Jan 18, 2015 7:58 am ]
Post subject:  Re: How many different pairing plans there are in round robi
Matti wrote:
This is the only pairing plan for four players. There is also only pairing plan for six player round robin. How many different pairing plans there are for eight player round robin?
I think you are asking for the number of 1-factorizations of the complete graph (up to isomorphism).
There are six. (And 396, 526915620, 1132835421602062347 for ten, twelve, fourteen players.)
https://oeis.org/A000474
Author:  Matti [ Tue Jan 20, 2015 1:43 am ]
Post subject:  Re: How many different pairing plans there are in round robi
zorq wrote:
Matti wrote:
This is the only pairing plan for four players. There is also only pairing plan for six player round robin. How many different pairing plans there are for eight player round robin?
I think you are asking for the number of 1-factorizations of the complete graph (up to isomorphism).
There are six. (And 396, 526915620, 1132835421602062347 for ten, twelve, fourteen players.)
https://oeis.org/A000474

Yes. This is what I was looking for.
Page 1 of 1 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/