For which sets of $(n, m, k)$ does there exist an edge-labelling (using $k$ labels) on $K_n$, such that every single-labelled subgraph is $K_m$?

Question

Or, equivalently - for what sets of $(n, m, k)$ is it possible, for a group* of $n$ people, to arrange $k$ days of "meetings", such that every day the group is split into subgroups of $m$ people, and every pair of people meets exactly once?

(This seems to be a general case of this question, where that question asks whether $(60, 6, 5)$ is a legal set of variables, though the first answer . The specific case when a friend asked me this question was for $(16, 4, ?)$ - and we quickly determined that $k$ would have to be $5$ if it was possible at all)

Since each person makes $m-1$ meetings every day, for $k$ days, and they need to meet $n-1$ other people, we have one constraint - $k(m-1) = n-1$

By the "argument from number of edges": $$ \begin{split} E(K_{n}) & = \frac{n(n-1)}{2}\\ k\cdot E(K_{m}) & = k\cdot\frac{m(m-1)}{2} \implies k\cdot\frac{m(m-1)}{2} = \frac{n(n-1)}{2} \implies m =n \end{split} $$ So now we can simplify the question to "For which sets of $(n, k)$ does there exist an edge-labelling (using $k$ labels) on $K_{n^2}$, such that every single-labelled subgraph is $K_n$?"

Applying the argument from number of edges again: $$ \begin{split} k\cdot E(K_{n}) & = k\cdot \frac{n(n-1)}{2}\\ E(K_{n^2}) & = \frac{n^2({n^2}-1)}{2} \implies k\cdot \frac{n(n-1)}{2} = \frac{n^2({n^2}-1)}{2}\\ &\qquad\qquad\quad\:\implies {n^4} - (k+1)\cdot{n^2} + k n = 0 \\ &\qquad\qquad\quad\:\implies {n^3} - (k+1)\cdot n + k = 0 \end{split} $$

At this point, I think I need to read up on how to find roots of a depressed cubic - but I'm posting here in case there's another, more elegant way that I've missed.

I've tagged this question as combinatorial-designs based on responses to that other question, even though I'm not familiar with the topic, so apologies if that's not correct.

---

EDIT: actually - have I missed something fundamental? The equation $m=n$ can be interpreted as "if $n$ people can meet each other exactly once by splitting into groups of $m$, $k$ times; then it can only happen if the subgroup is the same size as the larger group, and if $k=1$". Are there really no non-trivial solutions? The following (due to my friend, not me!) appears to be a counter-example:

$$ \begin{array} {|r|r|}\hline Day 1 & 1 & 2 & 3 & 4 & & 5 & 6 & 7 & 8 & & 9 & 10 & 11 & 12 & & 13 & 14 & 15 & 16 \\ \hline Day 2 & 1 & 5 & 9 & 13 & & 2 & 6 & 12 & 15 & & 3 & 7 & 10 & 16 & & 4 & 8 & 11 & 14 \\ \hline Day 3 & 1 & 6 & 11 & 16 & & 2 & 5 & 10 & 14 & & 3 & 8 & 12 & 13 & & 4 & 7 & 9 & 15 \\ \hline Day 4 & 1 & 7 & 12 & 14 & & 2 & 8 & 9 & 16 & & 3 & 5 & 11 & 5 & & 4 & 6 & 10 & 13 \\ \hline Day 5 & 1 & 8 & 10 & 15 & & 2 & 7 & 11 & 13 & & 3 & 6 & 9 & 14 & & 4 & 5 & 12 & 16 \\ \hline \end{array} $$

---

* "group/subgroup" in the natural language sense, not the algebraic sense

Answer 1

This is a standard problem in design theory. A Steiner system $S(t, k, v)$ is a pair $(X, B)$, where $X$ is a $v$-element set and $B$ is a set of $k$-subsets of $X$, called blocks, with the property that every $t$-element subset of $X$ is contained in a unique block.

In your notation, you are asking when $S(2,n,m)$ exists. There are obvious divisibility conditions: $m-1$ must divide $n-1$ and $\binom m2$ must divide $\binom n2$. Wilson proved in 1975 that those conditions are sufficient for any fixed $m$ if $n$ is large enough. Keevash greatly strengthened that type of asymptotic existence result. I think that a complete solution including all small values is still not available. Some cases that satisfy all simple conditions don't exist, such as $S(4, 5, 17)$.