3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ It turns out this notion is pretty well-studied, and corresponds to the affine plane. People are points, and meetings are lines. $\endgroup$
    – user44191
    Jun 2, 2020 at 20:21
  • $\begingroup$ 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. $\endgroup$
    – user44191
    Jun 2, 2020 at 22:53

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.