E    
  D  
    T

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 of order n consists of a set of n points and a collection of 3-element sets of points called triples, so that any two distinct points lie in a unique triple.

We abbreviate "Steiner triple system" to STS. There are trivial STSs of orders 0, 1 and 3.

We give here some of the most important results about Steiner triple systems.

Existence

Theorem (Kirkman): A Steiner triple system of order n exists if and only if n=0 or n is congruent to 1 or 3 mod 6.

The number n is called admissible if it satisfies the conditions of this theorem.

A Steiner triple system is called resolvable if the triples can be partitioned into sets called parallel classes, each of which is a partition of the set of points. A resolvable STS is also called a Kirkman triple system.

Theorem (Ray-Chaudhuri, Wilson): A Kirkman triple system of order n exists if and only if n=0 or n is congruent to 3 mod 6.

Enumeration

For small admissible n with n>3, the number of STS of order n (up to isomorphism) is given in the following table. The entries for n=15 and n=19 are due to White, Cole and Cummings, and to Kaski and Östergård, respectively.

n 7 9 13 15 19
Number 1 1 2 80 11084874829

Theorem (Wilson): The number of STS of order n, up to isomorphism, lies between (e-5n)n2/6 and nn2/6.

Theorem (Babai): Almost all STS of order n have trivial automorphism group.

Subsystems

A subsystem of a STS is a subset of the point set which contains the triple through any two of its points. A subsystem, together with the triples it contains, is a STS in its own right; we sometimes refer to this STS as being the subsystem.

Theorem (Doyen and Wilson): There exists a STS of order n with a subsystem of order m (where n and m are both admissible and m<n) if and only if n >= 2m+1.

Theorem (Doyen): For every admissible n, there exists a STS of order n which has no non-trivial proper subsystems.

STS with many subsystems

A triangle in a STS is a set of three points not forming a triple.

It is well-known that a STS in which every triangle lies in a 7-point subsystem is isomorphic to the points and lines of projective space over GF(2), and so has 2n-1 points, for some n.

Analogously we might expect that a STS in which every triangle lies in a 9-point subsystem is isomorphic to the points and lines of affine space over GF(3); but this is not so. The first counterexamples were found by Marshall Hall, so such STS are now called Hall triple systems, or HTS for short. They now have an extensive literature. It is true, however, that any HTS has 3n points, for some n.

Topological properties

An area of current interest involves embedding Steiner triple systems on surfaces. If a map, all of whose faces are triangles, is drawn on an orientable surface so that the vertices and edges form a complete graph, it may be possible to colour the faces with two colours in such a way that each edge lies in one face of each colour; then the faces of one colour form a Steiner triple system.

The simplest example is a map on the torus with 14 triangular faces, six meeting at each vertex, so that the 7 vertices and 21 edges form the complete graph K7; the faces can be partitioned into two copies of the 7-point STS.

Table of contents | Glossary | Topics | Bibliography | History

Peter J. Cameron
7 July 2003