Optimal round-robin schedule

[Chip Eastham]

Although tournament scheduling problems can involve some difficulties
in choosing opponents, a round-robin tournament avoids that headache
because every player (or team) plays every other one, pairwise.

Yet the situation is not entirely a simple one. Arguably one needs to
consider the frequency with which a competitor is scheduled. E.g.
having player 1 go against each of the others successively at the
outset might put player 1 at something of a disadvantage for lack of
rest.

A schedule can be devised in which no player competes twice in a row
if there are five players, but not if there are fewer.

Question: For a given gap g between competitions, is there a number N
s.t. for n >= N, a round-robin schedule exists where no player has two
competitions less than g places apart?


regards, chip

[Chip Eastham]

GENERALIZATION
==============

As the round-robin tournament involves all distinct
pairings of players (or teams), i.e. 2-subsets of the
"field" of competitors, a natural generalization is
to ask a similar question about k-subsets of {1,..,n}:

What sequence of all k-subsets maximizes the minimum
gap between any two with nonempty intersection?

SPOILER ALERT
=============

(Optimal gaps for round-robin tournament)

The answer is yes, we can arrange a round-robin schedule
where the minimum gap between appearances of a player is
(n/2) + O(1) for a field of n players. The minimum gap
can be arbitrarily large for sufficiently many players.

For n even the largest minimum gap is (n/2) - 1, while
for n odd the largest minimum gap is (n-1)/2. [The
specific case n=5 requires finding a Hamiltonian path
for the Petersen graph, in order to avoid scheduling a
player twice in consecutive competitions.]

[Round-robin tournament: Scheduling algorithm -- Wikipedia]
http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

The optimal gap for n even can be immediately derived
from the schedule described above. Optimal solutions
for n odd cannot, although the corresponding minimum
gap from the above approach is (n-1)/2 - 1, one less
than the optimum.

regards, chip