|
Encyclopaedia of DesignTheory: STS |
General | Partition | Incidence | Array |
Experimental | Other designs | Math properties | Stat properties |
Server | External | Bibliography | Miscellaneous |
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.
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.
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.
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.
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.
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