Steiner triple systems

A Steiner triple system (of order n) STS(n) is a 2-(n,3,1) design, that is, a Steiner system S(2,3,n), in other words, a collection of 3-subsets of an n-set such that any pair of elements of the n-set is contained in a unique one among these 3-sets.

As was shown by Kirkman, a Steiner triple system of order n exists if and only if either n = 0, 1, or n congruent to 1 or 3 (mod 6).

The unique Steiner triple system of order 7 is known as the Fano plane. It is the (unique) projective plane of order 2. The unique Steiner triple system of order 9 is the (unique) affine plane of order 3. Up to isomorphism, there are 2 Steiner triple systems of order 13, and 80 of order 15, and 11084874829 of order 19.

The block graph of a Steiner triple system is the graph with these 3-sets as vertices, where two 3-sets are adjacent when they have nonempty intersection. Such a graph is strongly regular, with parameters v = n(n – 1)/6, k = 3(n – 3)/2, λ = (n + 3)/2, μ = 9.

More generally, the block graph of a Steiner system S(2,m,n) is strongly regular.

Again more generally, the block graph of a quasi-symmetric design is strongly regular.

Reference

P. Kaski & P. R. J. Östergård, The Steiner Triple Systems of Order 19, Math. Comput. 73 (2004) 2075-2092.