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<=v<=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

Explore with Wolfram|Alpha


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. "Kirkman Parades." 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.

Referenced on Wolfram|Alpha

Kirkman Triple System

Cite this as:

Weisstein, Eric W. "Kirkman Triple System." From MathWorld--A Wolfram Web Resource.

Subject classifications