[1100] Designs exist!
By Gil Kalai
One of the central and oldest problems in combinatorics is: Can you find a collection S of q-subsets from an n-element set X so that every r-subset of X is included in precisely t sets in the collection? A collection S of this kind is called a design of parameters (n,q,r,t), a special interest is the case t = 1, and in this case S is called a Steiner system. It was conjectured that a design of parameters (n,q,r, t) exists for every q, r and t if n is sufficiently large and is admissible, namely if some necessary simple divisibility conditions are satisfied. Until recently the known constructions came very far from this.
Here is a brief history of the problem: The existence of designs and Steiner systems was asked by Plücker (1835), Kirkman (1846) and Steiner (1853). For r = 2 which was of special interest, Richard Wilson (1972-1975) proved their existence for large enough admissible values of n. Rödl (1985) proved the existence of approximate objects (the property holds for (1-o(1)) r-subsets of X), thus answering a conjecture by Erdös and Hanani. Teirlink (1987) proved their existence for infinitely many values of n when r and q are arbitrary and t is a certain large number depending on q and r but not on n. (His construction also does not have repeated blocks.) Keevash (2014) proved the existence of Steiner systems for all but finitely many admissible values of n for every q and r. He uses a new method referred to as Randomized Algebraic Constructions.
In the lecture I will describe the problem and its history and will try to explain some ingredients in the methods by Wilson, Rödl and Keevash.
[After Peter Keevash]