A foundational paper by Peter Keevash (Keevash 2014), first posted online in 2014, has now—twelve years later—been accepted for publication in the Annals of Mathematics. The paper proves the celebrated existence conjecture for combinatorial designs, resolving the central open problem of design theory.
One of the oldest results in combinatorics is Kirkman’s 1847 theorem (Kirkman 1847), which states that whenever the edges of the complete graph can be partitioned into edge-disjoint triangles. It is straightforward to verify that these congruence conditions are necessary. Kirkman’s theorem initiated several long-running research programmes. One of them gave rise to the area now known as design theory.
Let be an -element set, and let . A Steiner system is a collection of -element subsets of , called blocks, such that every -element subset of is contained in exactly one block. Thus, a decomposition of into edge-disjoint triangles is precisely an , usually called a Steiner triple system of order . Steiner systems are among the most elegant structures in combinatorics and have been studied since the work of Plücker in 1835, Kirkman in 1847, and Steiner in 1853. Before 2014, however, it was not known whether any nontrivial Steiner system with existed.
More generally, a family of -element subsets of is a combinatorial design with parameters if every -element subset of is contained in exactly members of . A Steiner system is therefore a combinatorial design with .
There are some immediate necessary conditions for the existence of such a design. In addition to , one must have Indeed, for any fixed -element subset of , the number of blocks containing it must be which must be an integer. When these conditions hold, we say that satisfies the divisibility conditions.
The famous existence conjecture for combinatorial designs asserted that these necessary divisibility conditions are also sufficient, provided that , , and are fixed and is sufficiently large. Kirkman’s theorem is the special case . Many further special cases were established over the following decades. In 1975, Wilson (Wilson 1975) proved the conjecture for , already a major achievement. For larger values of , however, the conjecture remained widely open, even when . In 2014, Keevash posted a paper (Keevash 2014) proving the conjecture in full generality.
The proof of Theorem builds on the work of Rödl (Rödl 1985). Answering a question posed by Erdős and Hanani in 1963 (Erdős and Hanani 1963), Rödl proved in 1985 that approximate designs can be constructed by a randomized greedy procedure. Such a construction covers almost every -element subset of , but it generally leaves a small collection of uncovered subsets. Keevash’s breakthrough was to combine this approximate construction with carefully designed randomized and algebraic ingredients that eliminate the remaining errors. He showed that the resulting process produces an exact combinatorial design with positive probability, thereby resolving the existence conjecture.