Steiner system

related topics
{math, number, function}
{@card@, make, design}
{line, north, south}

In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design. Specifically, S(l,m,n) is a (n,m,\frac{\tbinom{n-2}{l-2}}{\tbinom{m-2}{l-2}})-design.

A Steiner system with parameters l, m, n, written S(l,m,n), is an n-element set S together with a set of m-element subsets of S (called blocks) with the property that each l-element 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, q2+q+1), since it has q2+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 l-element subsets in S is \tbinom nl, while the number of l-element subsets in each block is \tbinom ml. Since every l-element subset is contained in exactly one block, we have \tbinom nl=b\tbinom ml, or b=\frac{\tbinom nl}{\tbinom ml}, where b is the number of blocks. Similar reasoning about l-element subsets containing a particular element gives us \tbinom{n-1}{l-1}=r\tbinom{m-1}{l-1}, or r=\frac{\tbinom{n-1}{l-1}}{\tbinom{m-1}{l-1}}, 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 b\ge n is true in Steiner systems.

Full article ▸

related documents
Subtraction
Malleability (cryptography)
Partial function
Calculus with polynomials
Byte-order mark
Algebraic extension
Extractor
Residue (complex analysis)
Iteration
Weierstrass–Casorati theorem
Hash collision
Zeta distribution
Double negative elimination
Borel-Cantelli lemma
Geometric mean
Degenerate distribution
Pseudometric space
Bernoulli process
Static code analysis
Abstract factory pattern
Nowhere dense set
Subalgebra
Waring's problem
Fibonacci coding
Heap (data structure)
Differential cryptanalysis
Bijection
Category (mathematics)
Alexandroff extension
Residue theorem