It is currently Tue Apr 16, 2024 11:09 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 7 posts ] 
Author Message
Offline
 Post subject: How many different pairing plans there are in round robin?
Post #1 Posted: Wed Jan 14, 2015 5:07 am 
Lives in gote

Posts: 309
Liked others: 3
Was liked: 41
Rank: 5 dan
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?

Top
 Profile  
 
Offline
 Post subject: Re: How many different pairing plans there are in round robi
Post #2 Posted: Wed Jan 14, 2015 8:04 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
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.


This post by HermanHiddema was liked by: ez4u
Top
 Profile  
 
Offline
 Post subject: Re: How many different pairing plans there are in round robi
Post #3 Posted: Thu Jan 15, 2015 4:08 am 
Lives in gote

Posts: 309
Liked others: 3
Was liked: 41
Rank: 5 dan
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.

Top
 Profile  
 
Offline
 Post subject: Re: How many different pairing plans there are in round robi
Post #4 Posted: Thu Jan 15, 2015 5:02 am 
Oza
User avatar

Posts: 2401
Location: Tokyo, Japan
Liked others: 2338
Was liked: 1332
Rank: Jp 6 dan
KGS: ez4u
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:

_________________
Dave Sigaty
"Short-lived are both the praiser and the praised, and rememberer and the remembered..."
- Marcus Aurelius; Meditations, VIII 21

Top
 Profile  
 
Offline
 Post subject: Re: How many different pairing plans there are in round robi
Post #5 Posted: Fri Jan 16, 2015 2:58 am 
Lives in gote

Posts: 309
Liked others: 3
Was liked: 41
Rank: 5 dan
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.

Top
 Profile  
 
Offline
 Post subject: Re: How many different pairing plans there are in round robi
Post #6 Posted: Sun Jan 18, 2015 7:58 am 
Beginner

Posts: 15
Liked others: 0
Was liked: 3
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

Top
 Profile  
 
Offline
 Post subject: Re: How many different pairing plans there are in round robi
Post #7 Posted: Tue Jan 20, 2015 1:43 am 
Lives in gote

Posts: 309
Liked others: 3
Was liked: 41
Rank: 5 dan
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.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: Bing [Bot] and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group