Kirkman Triple System

A Kirkman triple system of order $v=6n+3$ is a Steiner Triple System with parallelism (Ball and Coxeter 1987), i.e., one with the following additional stipulation: the set of $b=(2n+1)(3n+1)$ triples is partitioned into $3n+1$ components such that each component is a $(2n+1)$-subset of triples and each of the $v$ elements appears exactly once in each component. The Steiner Triple Systems of order 3 and 9 are Kirkman triple systems with $n=0$ and 1. Solution to Kirkman's Schoolgirl Problem requires construction of a Kirkman triple system of order $n=2$.

Ray-Chaudhuri and Wilson (1971) showed that there exists at least one Kirkman triple system for every Nonnegative order $n$. Earlier editions of Ball and Coxeter (1987) gave constructions of Kirkman triple systems with $9\leq v\leq 99$. For $n=1$, there is a single unique (up to an isomorphism) solution, while there are 7 different systems for $n=2$ (Mulder 1917, Cole 1922, Ball and Coxeter 1987).

See also Steiner Triple System

References

Abel, R. J. R. and Furino, S. C. ``Kirkman Triple Systems.'' §I.6.3 in The CRC Handbook of Combinatorial Designs (Ed. C. J. Colbourn and J. H. Dinitz). Boca Raton, FL: CRC Press, pp. 88-89, 1996.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 287-289, 1987.

Cole, F. N. Bull. Amer. Math. Soc. 28, 435-437, 1922.

Kirkman, T. P. ``On a Problem in Combinations.'' Cambridge and Dublin Math. J. 2, 191-204, 1847.

Lindner, C. C. and Rodger, C. A. Design Theory. Boca Raton, FL: CRC Press, 1997.

Mulder, P. Kirkman-Systemen. Groningen Dissertation. Leiden, Netherlands, 1917.

Ray-Chaudhuri, D. K. and Wilson, R. M. ``Solution of Kirkman's Schoolgirl Problem.'' Combinatorics, Proc. Sympos. Pure Math., Univ. California, Los Angeles, Calif., 1968 19, 187-203, 1971.

Ryser, H. J. Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 101-102, 1963.