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 or (recently) 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.[1] 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.[2][3][4]
- ^ "Encyclopaedia of Design Theory: t-Designs". Designtheory.org. 2004-10-04. Retrieved 2012-08-17.
- ^ Keevash, Peter (2014). "The existence of designs". arXiv:1401.3665 [math.CO].
- ^ Erica Kleirrach (2015-06-09). "A Design Dilemma Solved, Minus Designs". Quanta Magazine. Retrieved 2015-06-27.
- ^ Kalai, Gil. "Designs exist!" (PDF). Séminaire Bourbaki.