# How to maximize the number of people that mingle with each other?

Some motivation:

A company has a certain number of workers. On each given day from Monday to Friday, a fixed number of people are to work. The company wants to foster teamwork, bonding and camaraderie among its team, so it wants to create a weekly schedule that maximises the number of people that have worked with each other on at least one day. How can this be accomplished?

Formal problem (Graph theoretic version):

For $$n > 2$$, let $$G$$ be the edgeless graph on $$n$$ vertices. Let $$k > 1$$ be a given fixed positive integer. We are asked to select subsets $$A_1, \dots, A_k$$ of the vertex set of $$G$$ of cardinality $$m$$ each, where $$m < n$$ and $$km > n$$.

For each subset $$A_i$$, we connect all vertices in $$A_i$$ to each other. To be more precise, we form the graph $$G’$$ with vertex set that of $$G$$, and edge set $$E(G’) = \{(a, a’) \ | \ a, a’ ∈ A_i \text{ for some }i\}$$.

Question (GT): How can we maximise |E(G’)|? What is the maximum cardinality?

There is also a continuum/continuous version of the problem, which may be easier to deal with since it avoids problems with indivisibility of individual people.

Formal problem (Measure theoretic version):

Let $$X$$ be a non atomic measure space of measure $$1$$. For concreteness, we may take $$[0, 1]$$ under the Lebesgue measure.

Let $$k > 1$$ be a given fixed positive integer, and $$m$$ a real number with $$0 < m < 1$$ and $$km > 1$$. We are asked to select $$k$$ measurable subsets $$A_1, \dots , A_k$$ of $$X$$ of measure $$m$$.

Question (MT): Which choice of subsets maximises the measure of $$\cup_{i = 1}^n A_i \times A_i$$ in $$X \times X$$? What is the maximal measure?

Here we equip $$X \times X$$ with the product measure, and $$A_i \times A_i$$ denotes the set $$\{(a, a’) \ | \ a, a’ ∈ A_i\}$$.

Remark: By a compactness argument one can verify that the supremum is indeed achieved, and so we are justified in speaking of the configuration achieving the maximum.

For the finite version, note that the best that you could possibly do is if each pair is in at most one $$A_k$$. Design theorists know a lot about when such set families exist (Search Balanced Incomplete Block Designs) for parameters $$n,m$$, and $$k$$. For example, if $$m=q+1$$, $$n=q^2+q+1$$, and $$k \leq q^2+q+1$$, where $$q$$ is a prime power, then you can take $$A_1, \dots, A_k$$ to be a subset of lines of a finite projective plane over the finite field $$\mathbb{F}_q$$.
• Hm, each pair being in at most one $A_k$ may not be possible in the general case, depending on the values of $k, m, n$. Oh though I guess thats what you meant when you talked about existence of such families. Jul 16, 2021 at 7:28
Your $$m$$ is his $$r$$, but your $$n$$ and $$k$$ agree with his notation.
• Thank you for the reference! I will leave the question open just in case anyone wants to attempt the $k > 4$ case for now, but in the absence of any other answer I will accept yours. 2 days ago