## Speed dating and graph theory

Suppose you are organising a speed dating event. You are given a graph $G = (S,P)$. The event consists of a number of rounds; in the $i$th round of the event, you must pick a subset $P_i\in P$ such that no $s\in S$ appears in two elements of $P_i$, and $P_i\cap P_j = \varnothing$ for all $j < i$. (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 $R$ rounds, finishing when $\cup_{1\leq i\leq R} P_i = P$. (That is, when all possible dates have occurred). The ‘idle time’ is defined as $T = \sum_{1\leq i\leq R} \sum_{s\in S} 1(s \not\in p \forall p\in P_i)$.

For example, consider an event for $M$ straight men and $N$ straight women. Then $G$ is the complete bipartite graph $K_{M,N}$, 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, $R = \max(M,N)$ and $T = R |M-N|$.

How can you choose the $P_i$ to minimise $T$?