How many groups of people can we make with x number of overlaps?

Question

Say I have 120 people and I want to put them into unique groups of 6 without replacement where nobody knows each other.

It would be at minimum 120/6 + (120/6)/6 = 20 + (3.33) = ~ 23 (My reasoning here is that you could then take a single person from each of the 20 groups and put them in a new group to make an additional unique group)

Now say I allow one possible overlap meaning two people have already been in a group before. How would we calculate out the maximum number of unique groups? And what about if we allow for two overlaps (two pair of people have already been in a group before)?

Answer 1

You are looking for an $A(120,10,6)$ code, where the codewords have length $120$, weight $6$ and have distance at least $10$ from each other – each codeword corresponds to a group and the distance condition ensures that two groups can only have at most one person in common.

The Johnson bound for this parameter set is $460$. Here is a construction achieving $430$ codewords:

• Obtain $400$ codewords from an orthogonal array $OA(6,20)$, which is known to exist.
• The remaining edges form $6$ copies of $K_{20}$. In each of those complete graphs $5$ more $K_6$'s can be added, for a total of $30$ fill-in codewords.