0
$\begingroup$

Inspired by this question here:, I would conjecture that so long as there are 2n+1 teams involved in a round-robin tournament where each games consists of n-way teams, then a schedule is possible where no team plays back-to-back.

A number of round-robin schedules are given as solutions for 2-way games in the link above, with a couple of methods discussed. For example:

[[A, B], [D, E], [A, C], [B, D], [C, E], [A, D], [B, E], [C, D], [A, E], [B, C]]

solves the n=2-way game with 5 teams in the tournament.

For the n=3-way game I have found a solution with 7 teams, and suggest that a solution could be found for the n=4-way game with 9 teams.

3-way, 7 team solution:

1,4,6 ; 2,0,3 ; 1,4,5 ; 2,6,0 ; 3,4,5 ; 0,1,2 ; 6,3,4 ; 5,1,2 ; 6,4,0 ; 5,1,3 ; 4,0,2 ; 5,3,6 ; 4,0,1 ; 5,2,3 ; 6,0,1 ; 2,3,4 ; 1,5,6 ; 0,3,4 ; 1,6,2 ; 0,3,5 ; 6,2,4 ; 0,5,1 ; 6,2,3 ; 0,4,5 ; 1,2,3 ; 4,5,6 ; 3,0,1 ; 2,5,6 ; 3,1,4 ; 2,5,0 ; 3,6,1 ; 4,2,5 ; 3,6,0 ; 4,1,2 ; 5,6,0

There have been similar discussions previously, here and here but I believe this is the first time this precise question has been asked on stackexchange.

Anyone have an idea how to make any progress on the conjecture that such schedule solutions are possible for 2n+1 teams in n-way game tournaments?

$\endgroup$
  • $\begingroup$ One way to write this is that if you take a group $G$ with nodes being the $n$-element subsets of $\{1,2,\dots,2n+1\}$ and edges between disjoint nodes, can you find a Hamiltonian path in the graph. $\endgroup$ – Thomas Andrews Apr 2 at 17:19
0
$\begingroup$

This is equivalent to finding a Hamiltonian path in the Knesser graph $K(2n+1,n)$. This is the graph whose vertices are $n$ element subset of a $2n+1$ element set, where subsets are connected with an edge iff they are disjoint. According to Sparse Knesser Graphs are Hamiltonian, by Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak, this is possible for all $n\ge 3$. Since you already verified this for $n=2$, and it is obvious for $n=1$, it it true for all $n\ge 1$.

$\endgroup$
  • $\begingroup$ Thanks Mike - very helpful and answered the question perfectly. $\endgroup$ – MStander Apr 2 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.