Steiner system (original) (raw)

Definition. An S⁢(τ,κ,ν) Steiner system 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 symmetric 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 partition 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 groups M11 and M12 as their automorphism groups, 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 code and the Leech lattice.

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 space.