Monday 11 October 2010

co.combinatorics - Tournament formats

In light of the comments, I'll post an answer. It's probably not a homework question, but it's not exactly a research-level mathematics question either. The question was:




How many match ups must occur before everyone has sat out at least once or everybody has played everybody once?




Define the two teams {1,2,3,4,5,6} and {a,b,c,d,e,f}. In a volleyball context finding a solution is easy (as Gerhard "Ask Me About System Design" Paseman pointed out) -- mathematically, it is a collection of K4,4 subgraphs whose edges cover K6,6 such as



{1,2,3,4} x {a,b,c,d}
{1,2,5,6} x {a,b,e,f}
{3,4,5,6} x {c,d,e,f}.


If we interpret the original question in a strict sense (taking the word "or" literally), then two rounds would suffice.



I had a different interpretation of the question (which is slightly less trivial) which could be of interest to a chess tournament organiser, for example (often chess teams consist of 4 players with 2 reserves). That is, finding a decomposition of K6,6 into G≅4K1,1+4K1 such that each vertex is an isolated vertex in at least one G. Since G has 4 edges and K6,6 has 62=36 edges. We deduce that we need 36/4=9 rounds (i.e. components). Here's the solution I found (via a randomised algorithm using GAP)



match-up      byes
1a 3c 4e 6b 2 5 d f
1b 2e 4c 5d 3 6 a f
1c 3e 5a 6f 2 4 b d
1d 2c 3b 6e 4 5 a f
1e 2d 5f 6a 3 4 b c
1f 2a 4b 5e 3 6 c d
2b 3f 4a 6d 1 5 c e
2f 3a 4d 5c 1 6 b e
3d 4f 5b 6c 1 2 a e


I just noticed that the byes are balanced, that is each player has a bye in three rounds.



Neither of the above interpretations uses the graph-theoretic interpretation of tournament.

No comments:

Post a Comment