Balanced tournament designs
Suppose you have an even number of teams that you'd like to schedule in a Round Robin tournament. This means each team plays every other team exactly once.
Denote the number of teams as 2n. You'd like each team to play in each round, so you need n locations for the games to be played.
Each game will choose 2 teams from the set of 2n teams, so the number of games will be n(2n - 1). And this means you'll need 2n - 1 rounds. A tournament design will be a grid with n rows, one for each location, and 2n-1 columns, one for each round.
Let's pause there for just a second and make sure this is possible. We can certainly assign n(2n - 1) games to a grid of size n by 2n-1. But can we do it in such a way that no team needs to be in two locations at the same time? It turns out we can.
Now we'd like to introduce one more requirement: we'd like to balance the games over the locations. By that we mean we'd like a team to play no more than twice in the same location. A team has to play at least once in each location, but not every team can play twice in each location. If every team played once in each location, we'd have n^2 games, and if every team played twice in each location we'd have 2n^2 games, but
n^2 < n(2n - 1) < 2n^2
for n greater than 1. If n = 1, this is all trivial, because in that case we would have two teams. They simply play each other and that's the tournament!
We can't have each team play exactly the same number of times in each location, but can we have each team play either once or twice in each location? If so, we call that a balanced tournament design.
Now the question becomes for which values of n can we have a balanced tournament design involving 2n teams. This is called a BTD(n) design.
We said above that this is possible if n = 1: two teams just play each other somewhere. For n = 2, it is not possible to have a balanced tournament design: some team will have to play all three games in the same location.
It is possible to have a balanced tournament design for n = 3. Here's a solution:
In fact this is the solution aside from relabeling the teams. That is, given any balanced tournament design involving six teams, there is a way to label the teams so that you have the design above. Said another way, there is one design in BTD(3) up to isomorphism.
There are balanced tournament designs for all positive n except for n = 2. And in general there are a lot of them. There are 47 designs in BTD(4) up to isomorphism [1].
Related posts[1] The CRC Handbook of Combinatorial Designs. Colbourn and Dinitz editors. CRC Press, 1996.
The post Balanced tournament designs first appeared on John D. Cook.