Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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".

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

$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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.