Steiner system


Definition. An S(τ,κ,ν) Steiner systemMathworldPlanetmath is a τ-(ν,κ,1) design (i.e. λ=1). The values τ,κ,ν are the parameters of the Steiner system.

Since λ=1, a Steiner system is a simple design, and therefore we may interpret a block to be a set of points (B=𝒫B), which we will do from now on.

Given parameters τ,κ,ν, there may be several non-isomorphic systems, or no systems at all.

Let 𝒮 be an S(τ,κ,ν) system with point set 𝒫 and block set , and choose a point P𝒫 (often, the system is so symmetricMathworldPlanetmath that it makes no difference which point you choose). The choice uniquely induces an S(τ-1,κ-1,ν-1) system 𝒮1 with point set 𝒫1=𝒫{P} and block set 1 consisting of B{P} for only those B that contained P. This works because for any T1𝒫1 with |T1|=τ-1 there was a unique B that contained T=T1{P}.

This recurses down all the way to τ=1 (a partitionMathworldPlanetmath of ν-τ+1 into blocks of κ-τ+1) and finally to τ=0 (one arbitrary block of κ-τ). If any of the divisibility conditions (see the entry design (http://planetmath.org/Design) for more detail) on the way there do not hold, there cannot exist a Steiner system with the original parameters either.

For instance, Steiner triple systems S(2,3,ν) (the first Steiner systems studied, by Kirkman, before Steiner) exist for ν=0 and all ν1 or 3(mod6), and no other ν.

The reverse construction, turning an S(τ,κ,ν) into an S(τ+1,κ+1,ν+1), need not be unique and may be impossible. Famously an S(4,5,11) and a S(5,6,12) have the Mathieu groupsMathworldPlanetmath M11 and M12 as their automorphism groupsMathworldPlanetmathPlanetmath, while M22, M23 and M24 are those of an S(3,6,22), S(4,7,23) and S(5,8,24), with connexions to the binary Golay codeMathworldPlanetmath and the Leech latticeMathworldPlanetmath.

Remark. A Steiner system S(t,k,n) can be equivalently characterized as a k-uniform hypergraph on n vertices such that every set of t vertices is contained in exactly one edge. Notice that any S(2,k,n) is just a k-uniform linear spacePlanetmathPlanetmath.

Title Steiner system
Canonical name SteinerSystem
Date of creation 2013-03-22 13:05:37
Last modified on 2013-03-22 13:05:37
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 9
Author mathcam (2727)
Entry type Definition
Classification msc 51E10
Classification msc 05C65
Related topic Hypergraph
Related topic IncidenceStructures
Defines Steiner triple system