
Encyclopaedia of DesignTheory: STS 
General  Partition  Incidence  Array 
Experimental  Other designs  Math properties  Stat properties 
Server  External  Bibliography  Miscellaneous 
We regard an STS of order 3 or less as trivial.
In other words, a nontrivial STS is a 2(n,3,1) design, that is, the special case t=2, k=3, l=1 of a tdesign.
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 nontrivial STS is 7. There is up to isomorphism a unique STS of order 7. It can be represented in various nice ways:
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 RayChaudhuri 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