# 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$?

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

• It turns out this notion is pretty well-studied, and corresponds to the affine plane. People are points, and meetings are lines. Jun 2, 2020 at 20:21
• Also: $n = 1$ is a solution to your cubic (one person is every meeting), so it reduces to $n^2 + n - k = 0$. This should be clear from factoring the earlier equation. Jun 2, 2020 at 22:53

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