Encyclopaedia of DesignTheory: STS

General Partition Incidence Array
Experimental Other designs Math properties Stat properties
Server External Bibliography Miscellaneous

Steiner triple systems

A Steiner triple system consists of a set X of n points, and a collection B of subsets of X called blocks or triples, such that each block contains exactly 3 points, and any two points lie together in exactly one block. We abbreviate "Steiner triple system" to STS; the number n of points is its order.

We regard an STS of order 3 or less as trivial.

In other words, a non-trivial STS is a 2-(n,3,1) design, that is, the special case t=2, k=3, l=1 of a t-design.

One of the oldest results in design theory is Kirkman's existence theorem for Steiner triple systems: a STS of order n exists if and only if n is congruent to 1 or 3 mod 6. (Kirkman's proof predated Steiner's proposing the problem by several years; by rights they should be called "Kirkman triple systems", but this term is used for a special case, as we will see.) Numbers n of this form are called admissible orders for Steiner triple systems.

Thus, the smallest admissible order of a non-trivial STS is 7. There is up to isomorphism a unique STS of order 7. It can be represented in various nice ways:

This system is also known as the projective plane of order 2, or the Fano plane. (Paradoxically, Fano had studied projective planes not containing this configuration!)

A Kirkman triple system is a resolvable Steiner triple system; that is, one whose blocks can be partitioned into "parallel classes" so that each point lies on a unique block of each parallel class. Kirkman's "schoolgirl problem" asked for the set of orders of such systems. Clearly the order must be divisible by 3.

For n=9, there is a unique Steiner triple system, which is a Kirkman system; it is otherwise known as the affine plane of order 3. Taking the points as the cells of a 3 x 3 matrix, the blocks are the rows, the colummns, and the six triples corresponding to the terms in the determinant of the matrix. Another representation takes the points to be the pairs of elements from the integers mod 3; the blocks are all sets of three distinct pairs having sum zero.

Explicitly, the point set is {1,2,...,9}, and the blocks (grouped in parallel classes) are {1,2,3}, {4,5,6}, {7,8,9}; {1,4,7}, {2,5,8},{3,6,9}; {1,5,9}, {2,6,7}, {3,4,8}; {1,6,8}, {2,4,9}, {3,5,7}.

More than a century after the problem was posed by Kirkman, it was solved by Ray-Chaudhuri and Wilson: a Kirkman triple system of order n exists for all n congruent to 3 mod 6.

Table of contents | Glossary | Topics | Bibliography | History

Peter J. Cameron
16 April 2002