The existence conjecture for combinatorial designs is true

You need to know: Factorial n!=1\cdot 2 \cdot \dots \cdot n with convention that 0!=1, notation {n}\choose{k} for \frac{n!}{k!(n-k)!}.

Background: We say that a family S of q-elements subsets of an n-element set X is a (combinatorial) design with parameters (n, q, r, \lambda) if every r-element subset of X belongs to exactly \lambda sets in S. We say that positive integers (n, q, r, \lambda) satisfy the divisibility conditions if r\leq q \leq n and {{q-i}\choose{r-i}} divides \lambda{{n-i}\choose{r-i}} for every 0\leq i \leq r-1.

The Theorem: On 15th January 2015, Peter Keevash submitted to arxiv a paper in which he proved that for any fixed positive integers q, r, and \lambda, there exist n_0=n_0(q, r, \lambda) such that if n \geq n_0 and (n, q, r, \lambda) satisfy the divisibility conditions then a design with parameters (n, q, r, \lambda) exists.

Short context: The statement of the Theorem was known as the existence conjecture for combinatorial designs and was the central open question in design theory. In 1975, Wilson proved this conjecture for r=2, which already was recognised as a major achievement. The Theorem proves the conjecture in general. The result is new even for \lambda=1, in which case combinatorial design is called Steiner system. Steiner systems are studied since work of Plücker (1835), Kirkman (1846) and Steiner (1853), but, before the Theorem was proved, there was not even known if any single Steiner system with r>5 exists. See here for a related resent result.

Links: Free arxiv version of the original paper is here.

Go to the list of all theorems

One thought on “The existence conjecture for combinatorial designs is true

Leave a comment