Here is one of the central and oldest problems in combinatorics:
Problem: Can you find a collection S of q-subsets from an n-element set X set so that every r-subset of X is included in precisely λ sets in the collection?
A collection S of this kind are called a design of parameters (n,q,r, λ), a special interest is the case λ=1, and in this case S is called a Steiner system.
For such an S to exist n should be admissible namely 
There are only few examples of designs when r>2. It was even boldly conjectured that for every q r and λ if n is sufficiently large than a design of parameters (n,q,r, λ) exists but the known constructions came very very far from this. … until last week. Last week, Peter Keevash gave a twenty minute talk at Oberwolfach where he announced the proof of the bold existence conjecture. Today his preprint the existence of designs, have become available on the arxive.
Brief history
The existence of designs and Steiner systems is one of the oldest and most important problems in combinatorics.
1837-1853 – The existence of designs and Steiner systems was asked by Plücker(1835), Kirkman (1846) and Steiner (1853).
1972-1975 – For r=2 which was of special interests, Rick Wilson proved their existence for large enough admissible values of n.
1985 -Rödl 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.
1987 – Teirlink proved their existence for infinitely many values of n when r and q are arbitrary and λ is a certain large number depending on q and r but not on n. (His construction also does not have repeated blocks.)
2014 – Keevash’s 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 Randomised Algebraic Constructions.
Update: Just 2 weeks before Peter Keevash announced his result I mentioned the problem in my lecture in “Natifest” in a segment of the lecture devoted to the analysis of Nati’s dreams. 35:38-37:09.
Update: Some other blog post on this achievement: Van Vu, Jordan Ellenberg, The aperiodical . A related post from Cameron’s blog Subsets and partitions.
Update: Danny Calegary pointed out a bird-eye similarity between Keevash’s strategy and the strategy of the recent Kahn-Markovic proof of the Ehrenpreis conjecture http://arxiv.org/abs/1101.1330 , a strategy used again by Danny and Alden Walker to show that random groups contain fundamental groups of closed surfaces http://arxiv.org/abs/1304.2188 .
Combinatorics and more 
Interesting result. However, the notion of “a design” seems to be used also in other settings. I’m wondering the design you are talking about (with the prescribed parameters) the same as the designs we know, e.g., from Nissan-Wigderson, etc. ?
There are a lot of designs out there, but these can be said to be the main type, also called balanced inkomplete block designs (BIBD).
It is also very interesting to study designs when q is not fixed but increases with n. These regime includes already for r=2 the famous question on the existence of finite projective spaces (of order which is not a prime-power ) as a special case.
A beautiful application of probabilistic reasoning in this regime is described in two recent papers by Kuperberg, Lovett, and Peled. http://front.math.ucdavis.edu/1111.0492 and http://front.math.ucdavis.edu/1302.4295 .
Hi Gil, I wrote short introduction for the proof http://vuhavan.wordpress.com/2014/01/14/existence-of-designs/, explaining a few basic ideas here.
MAny thanks, Van. Let me also recommend your post about the Oberwolfach meeting
Just 2 weeks before Peter Keevash announced his result I mentioned the problem in my lecture in “Natifest” in a segment of the lecture devoted to the analysis of Nati’s dreams. http://www.youtube.com/watch?v=1rOMQEgmIi4&list=PLT-roSWIpp1H548vslNiRuDYUKZZhw31i&index=4 35:38-37:09
Pingback: The existence of designs | Quomodocumque
Pingback: Proof News: Designs exist! | The Aperiodical
The method of construction is extremely interesting to me in its general outline, of first doing a random construction which “nearly” solves the combinatorial problem, and then adjusting the result around the margins by formally expressing the error as a linear combination of formal “differences” of designs of uniformly bounded size, and then treating “negative” quantities of these small designs as “holes” in the big uniform quantity.
Exactly the same idea (at this abstract level) is the key to the recent Kahn-Markovic proof of the Ehrenpreis conjecture http://arxiv.org/abs/1101.1330 where one first uses a probabilistic (i.e. ergodic theoretic) argument to covers a hyperbolic surface with an almost equidistributed collection of “pairs of pants” with an almost prescribed geometry, almost all of which can be glued up, and then shows that the error can be formally glued up if one uses “negative” pieces, which one then interprets as holes in big uniform collection (I like to think of these “negative” pants as “holes in the Dirac pants sea” . . .)
Exactly the same idea again was used by Alden Walker and I recently to show that random groups contain fundamental groups of closed surfaces http://arxiv.org/abs/1304.2188 we first build “most” of the surface by a random matching argument, then glue up the error formally using “negative” pieces (of bounded size), which can then be pulled out of the collection that was already matched.
No doubt the details of the constructions diverge considerably beyond this “family resemblance” (this is already true in the latter two examples, where I understand the details of what is going on), but this resemblance at the abstract level seems to me to be much more than a triviality.
Dear Danny, this is a very interesting point of view and I’d love to understand it better. To a little extent Wilson’s proof for the case r=2 had also some flavour of this kind. We are familiar with randomness+structure compositions as a major paradigm in proving properties of arbitrary sets so in some sense the underlying motive you point out is a combination of randomness+structure (where the structure is algebraic) for constructions!.
Pingback: 3-manifolds everywhere | Geometry and the imagination
Pingback: Midrasha Mathematicae #18: In And Around Combinatorics | Combinatorics and more
Pingback: Séminaire N. Bourbaki – Designs Exist (after Peter Keevash) – the paper | Combinatorics and more
Pingback: Amazing: Stefan Glock, Daniela Kühn, Allan Lo, Deryk Osthus give a new proof for Keevash’s Theorem. And more news on designs. | Combinatorics and more
Pingback: Peter Keevash: More and Easier Designs! | Combinatorics and more
Pingback: Ringel Conjecture, Solved! Congratulations to Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov | Combinatorics and more