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

Question

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.

Answer 1

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

Answer 2

This is the problem of finding optimal partial edge clique coverings. See

Damaschke, P. Optimal partial clique edge covering guided by potential energy minimization. Optim Lett 13, 1469–1481 (2019). https://doi.org/10.1007/s11590-019-01469-y

Your $m$ is his $r$, but your $n$ and $k$ agree with his notation.