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.


2 Answers 2


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

  • $\begingroup$ 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. $\endgroup$
    – Nate River
    Jul 16, 2021 at 7:28
  • 1
    $\begingroup$ Yes, such families do not always exist, so this is not a complete answer. It does give an infinite set of parameters for which the obvious upper bound can actually be achieved. $\endgroup$
    – Tony Huynh
    Jul 16, 2021 at 7:32

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.

  • $\begingroup$ 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. $\endgroup$
    – Nate River
    2 days ago

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .