In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design. Specifically, S(l,m,n) is a design.
A Steiner system with parameters l, m, n, written S(l,m,n), is an nelement set S together with a set of melement subsets of S (called blocks) with the property that each lelement subset of S is contained in exactly one block. A Steiner system with parameters l, m, n is often called simply "an S(l,m,n)".
An S(2,3,n) is called a Steiner triple system, and its blocks are called triples. The number of triples is n(n−1)/6. We can define a multiplication on a Steiner triple system by setting aa = a for all a in S, and ab = c if {a,b,c} is a triple. This makes S into an idempotent commutative quasigroup.
An S(3,4,n) is sometimes called a Steiner quadruple system. Systems with higher values of m are not usually called by special names.
Contents
Examples
Finite projective planes
A finite projective plane of order q, with the lines as blocks, is an S(2, q+1, q^{2}+q+1), since it has q^{2}+q+1 points, each line passes through q+1 points, and each pair of distinct points lies on exactly one line.
Properties
It is clear from the definition of S(l,m,n) that 1 < l < m < n. (Equalities, while technically possible, would lead to trivial systems.)
If S(l,m,n) exists, then taking all blocks containing a specific element and discarding that element gives a derived system S(l−1,m−1,n−1). Therefore the existence of S(l−1,m−1,n−1) is a necessary condition for the existence of S(l,m,n).
The number of lelement subsets in S is , while the number of lelement subsets in each block is . Since every lelement subset is contained in exactly one block, we have , or , where b is the number of blocks. Similar reasoning about lelement subsets containing a particular element gives us , or , where r is the number of blocks containing any given element. From these definitions follows the equation bm = rn. It is a necessary condition for the existence of S(l,m,n) that b and r are integers. As with any block design, Fisher's inequality is true in Steiner systems.
Full article ▸
