1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ FWIW this can also be phrased in terms of disjoint perfect matchings of a complete graph. $\endgroup$ – Peter Taylor Oct 16 '17 at 12:00
3
$\begingroup$

It is possible to get stuck. If you do ax, by, and cz in Round 1, then ay, bz, and cx in Round 2, and az, bx, cy in Round 3, there is no way to make three matches in Round 4.

I saw this happen in a "hexagonal" chess tournament some years ago, when the organizer got careless with the matchups.

$\endgroup$
  • $\begingroup$ Oh, well that was a much less interesting problem than I thought it would be! Thanks. $\endgroup$ – David Z Oct 16 '17 at 5:23
0
$\begingroup$

As has been pointed out, you are investigating $1$-factorizations of $K_{2n}$ (or non-isomorphic ones) and no, partial $1$-factoizations may fail to extend to $1$-factorizations as has been pointed out.

You may also be interested in the Kirkman Schoolgirl Problem which asks the following related question: given $15$ (or $n = 3+6k$) students in a science class and the $7$ ($(n-1)/2$) lab days in the school year, can you design a partition for each lab day of the students into $5$ ($n/3$) lab groups of size $3$ so that each pair of students is in a lab group together exactly once? Indeed, such constructions known as resolvable Steiner triple systems of order $3+6k$ or Kirkman triple systems are known.

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