I'm thinking about the problem of partitioning a set into subsets of size 2 (i.e. pairs), and then doing so repeatedly without repeating a pair that has occurred in a previous partition. This was inspired by this Stack Overflow question about pairing students in a class each week so that no two students work together more than once, a problem which has also been addressed here on this site (directly [1] as well as by related questions [2, 3, 4]).
If I understand correctly, if I'm partitioning a set of size $n$ into pairs, it's always possible to choose $(n - 1)$ such partitions such that no pair occurs twice among them, e.g. as in a round robin tournament. In the motivating example, given a class of $n$ students, this would mean that every student works with every other student exactly once over the course of $n - 1$ weeks.
But I'm wondering about an aspect I haven't seen asked in another question: suppose $m < n - 1$ partitions are already given. The $m$ partitions are completely arbitrary except that no pair is repeated among them. Is it always possible to choose $n - 1 - m$ additional partitions such that, when considering the given partitions and the additional ones together, no pair is repeated among them? Or is it possible to get "stuck" and be unable to choose enough partitions without repeating a pair?
If I may attempt a more precise formulation: (I'm not a mathematician, so apologies for any abuses of notation)
Let $S$ be a set of $n$ distinct elements, where $n$ is even
Example: $S = \{1,2,3,4,5,6\}$
Let $P$ denote a 2-partition of $S$, i.e. a partition of $S$ into 2-element subsets (pairs), with each element of $S$ occurring in exactly one pair in $P$
Examples: $$\begin{align} P_1 &= \{\{1,2\},\{3,4\},\{5,6\}\} \\ P_2 &= \{\{1,3\},\{2,5\},\{4,6\}\} \\ P_3 &= \{\{1,5\},\{3,4\},\{2,6\}\} \end{align}$$
Let $T$ denote a set of 2-partitions of $S$. To adapt another question's terminology, let's say that $T$ is "fresh" if no pair is repeated among all the partitions in the set. (Much like what this other question terms "orthogonal".)
Examples: $$\begin{align} &\text{Fresh} & &\text{Not Fresh} \\ T_1 &= \{P_1, P_2\} & T_3 &= \{P_1, P_3\} \\ T_2 &= \{P_2, P_3\} & T_4 &= \{P_1, P_2, P_3\} \end{align}$$
- Borrowing from yet another question, let $w(n, 2)$ denote the size of the largest possible fresh set of 2-partitions of $S$. Obviously $w(n, 2) \leq n - 1$, and I believe $w(n, 2) = n - 1$ for any $n$ but I'm not totally sure. (Of course $w(n, k)$ for arbitrary $k > 2$ is an open problem.)
- Given a fresh set of 2-partitions $T$, we say that $T$ is complete if $\lvert T\rvert = w(n, 2)$, or incomplete if $\lvert T\rvert < w(n, 2)$.
Then my question boils down to this: given any incomplete fresh set of 2-partitions $T = \{P_1, \ldots, P_m\}$ with $m < w(n, 2)$, is it always possible to choose partitions $P_{m+1},\ldots,P_{w(n,2)}$ such that $\{P_1,\ldots,P_m,P_{m+1},\ldots,P_{w(n,2)}\}$ is complete?
Or more succinctly, is every incomplete fresh set a subset of a complete fresh set?
I suspect that the answer is affirmative, and that a straightforward proof exists, but I'm kind of burned out and can't think of it. I'm interested in either an intuitive demonstration or an actual proof, or both.
