Kirkman Triple Matching

A Kirkman Triple System is a \(\left(v, 3, 1\right)\)-\(\mathrm{RBIBD}\) named for Kirkman’s schoolgirl problem: a special case of perfect stranger matching where \(\alpha = 5\) and \(\beta = 3\). It was shown by Ray-Chaudhuri and Wilson (1971)¹ that such systems are constructible where the total number of elements is an odd multiple of 3. This is equivalent to saying that \(l_{\max}(\alpha, 3)\) is equal to the trivial upper bound when \(\alpha\) is odd.

Constructions

Ray-Chaudhuri and Wilson (1971) detail several theorems which can be used to construct Kirkman triple systems for different cases. Those described here are the ones which are currently implemented as part of the perfect-strangers package (hopefully one day I’ll get round to implementing them all).

Composition Theorems

Theorems 3 and 4 from Ray-Chaudhuri and Wilson (1971) provide constructions for Kirkman triple systems based on the composition of balanced incomplete block designs of smaller sizes and resolvable orthogonal arrays.

Theorem 4

Theorem 4 is the technique used for \(\mathrm{Sub}\)-\(\mathrm{RBIBD}\) matching.

Primitive Element Theorems

Theorems 5 and 6 from Ray-Chaudhuri and Wilson (1971) are instances of primitive element constructions.