Algorithm for a group of people meeting each other person in the least amount of iterations

Question

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

Answer 1

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