3
$\begingroup$

In my specific case, I have a pool of 80 people that I will be splitting into groups of 4. I would like to rotate people through the groups in a way that each person meets every other person in the least amount of iterations. It is ok to have met the same person multiple times.

In a generic case, if I have K people in a pool in groups of size N, what is the most efficient way for each individual to met every other individual.

I have dont searches on speed dating and speed networking and haven't found a solution that works for groups larger than 2. Is there a name for this particular problem? A similar problem I found was the "Social Golfer Problem", but my problem differs in that there can be some overlap in who you "meet".

$\endgroup$
4
$\begingroup$

$K_n$ denotes the complete graph on $n$ vertices. You are asking for the $K_4$-covering number of $K_8$, which is denoted by $C( K_4, K_80)$. Edges are allowed to be covered several times.

Your general case corresponds to $C(K_n, K_k)$. [Note that often $n$ and $k$ are often reversed in the literature, i.e. there are $N$ people, and we have groups of size $K$.]

The exact value has been solved for $n=3, 4$, but is open for $n=5$.

For $n=3$, check out M.U. Fort and G.A. Hedlund, Minimal coverings of pairs by triangles

For $n=4$, check out W.H. Mills, On the covering of pairs by quadruples-I, J

For covering by a general graph $H$, and large enough values of $k$, $C(H, K_k)$ has been determined. You can check out Covering Graphs: The covering problem solved by Yair Caro, Raphael Yuster.

$\endgroup$

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.