Steiner System - Properties

Properties

It is clear from the definition of S(t,k,n) that . (Equalities, while technically possible, lead to trivial systems.)

If S(t,k,n) exists, then taking all blocks containing a specific element and discarding that element gives a derived system S(t−1,k−1,n−1). Therefore the existence of S(t−1,k−1,n−1) is a necessary condition for the existence of S(t,k,n).

The number of t-element subsets in S is, while the number of t-element subsets in each block is . Since every t-element subset is contained in exactly one block, we have, or, where b is the number of blocks. Similar reasoning about t-element 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 . It is a necessary condition for the existence of S(t,k,n) that b and r are integers. As with any block design, Fisher's inequality is true in Steiner systems.

Given the parameters of a Steiner system S(t,k,n) and a subset of size, contained in at least one block, one can compute the number of blocks intersecting that subset in a fixed number of elements by constructing a Pascal triangle. In particular, the number of blocks intersecting a fixed block in any number of elements is independent of the chosen block.

It can be shown that if there is a Steiner system S(2,k,n), where k is a prime power greater than 1, then n 1 or k (mod k(k−1)). In particular, a Steiner triple system S(2,3,n) must have n = 6m+1 or 6m+3. It is known that this is the only restriction on Steiner triple systems, that is, for each natural number m, systems S(2,3,6m+1) and S(2,3,6m+3) exist.