Steiner system

In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design, specifically a t-design with λ = 1 and t ≥ 2. In combinatorial mathematics, a Steiner system (named after Jakob Steiner) is a type of block design, specifically a t-design with λ = 1 and t ≥ 2. A Steiner system with parameters t, k, n, written S(t,k,n), is an n-element set S together with a set of k-element subsets of S (called blocks) with the property that each t-element subset of S is contained in exactly one block. In an alternate notation for block designs, an S(t,k,n) would be a t-(n,k,1) design. This definition is relatively new. The classical definition of Steiner systems also required that k = t + 1. An S(2,3,n) was (and still is) called a Steiner triple (or triad) system, while an S(3,4,n) is called a Steiner quadruple system, and so on. With the generalization of the definition, this naming system is no longer strictly adhered to. Long-standing problems in design theory were whether there exist any nontrivial Steiner systems (nontrivial meaning t < k < n) with t ≥ 6; also whether infinitely many have t = 4 or 5. Both existences were proved by Peter Keevash in 2014. His proof is non-constructive and, as of 2019, no actual Steiner systems are known for large values of t. 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. A finite affine plane of order q, with the lines as blocks, is an S(2, q, q2). An affine plane of order q can be obtained from a projective plane of the same order by removing one block and all of the points in that block from the projective plane. Choosing different blocks to remove in this way can lead to non-isomorphic affine planes. An S(3,4,n) is called a Steiner quadruple system. A necessary and sufficient condition for the existence of an S(3,4,n) is that n ≡ {displaystyle equiv } 2 or 4 (mod 6). The abbreviation SQS(n) is often used for these systems. Up to isomorphism, SQS(8) and SQS(10) are unique, there are 4 SQS(14)s and 1,054,163 SQS(16)s. An S(4,5,n) is called a Steiner quintuple system. A necessary condition for the existence of such a system is that n ≡ {displaystyle equiv } 3 or 5 (mod 6) which comes from considerations that apply to all the classical Steiner systems. An additional necessary condition is that n ≢ {displaystyle ot equiv } 4 (mod 5), which comes from the fact that the number of blocks must be an integer. Sufficient conditions are not known. There is a unique Steiner quintuple system of order 11, but none of order 15 or order 17. Systems are known for orders 23, 35, 47, 71, 83, 107, 131, 167 and 243. The smallest order for which the existence is not known (as of 2011) is 21. An S(2,3,n) is called a Steiner triple system, and its blocks are called triples. It is common to see the abbreviation STS(n) for a Steiner triple system of order n. The total number of pairs is n(n-1)/2, of which three appear in a triple, and so the total number of triples is n(n−1)/6. This shows that n must be of the form 6k+1 or 6k + 3 for some k. The fact that this condition on n is sufficient for the existence of an S(2,3,n) was proved by Raj Chandra Bose and T. Skolem. The projective plane of order 2 (the Fano plane) is an STS(7) and the affine plane of order 3 is an STS(9). Up to isomorphism, the STS(7) and STS(9) are unique, there are two STS(13)s, 80 STS(15)s, and 11,084,874,829 STS(19)s.