Suppose you are organising a speed dating event. You are given a graph . The event consists of a number of rounds; in the
th round of the event, you must pick a subset
such that no
appears in two elements of
, and
for all
. (That is, no person may be in two dates at the same time, and the same date may not occur in two rounds.) The event lasts for
rounds, finishing when
. (That is, when all possible dates have occurred). The ‘idle time’ is defined as
.
For example, consider an event for straight men and
straight women. Then
is the complete bipartite graph
, and a simple solution is to have all the men seated around the inside of a ring-shaped table, all the women around the outside, and to have one set rotate around after each round while the other set stays still. In this case,
and
.
How can you choose the to minimise
?