# Séminaire N. Bourbaki – Designs Exist (after Peter Keevash) – the paper

On June I gave a lecture on Bourbaki’s seminare devoted to Keevash’s  breakthrough result on the existence of designs. Here is a draft of the paper: Design exists (after P. Keevash).

Remarks, corrections  and suggestions are most welcome!

I would have loved to expand a little on

1) How designs are connected to statistics

2) The algebraic part of Keevash’s proof

3) The “Rodl-style probabilistic part” (that I largely took for granted)

4)   The greedy-random method in general

5)  Difficulties when you move from graph decomposition to hypergraph decomposition

6) Wilson’s proofs of his theorem

7) Teirlink’s proof of his theorem

I knew at some point in rough details both Wilson’s proof (I heard 8 lectures about and around it from Wilson himself  in 1978) and Teirlink’s (Eran London gave a detailed lecture at our seminar) but I largely forgot, I’d be happy to see a good source).

8) Other cool things about designs that I should mention.

9) The Kuperberg-Lovett-Peled work

(To be realistic, adding something for half these items will be nice.)

Here is the seminar page,  (with videotaped lectures), and the home page of Association des collaborateurs de Nicolas Bourbaki . You can find there cool links to old expositions since 1948 which overall give a very nice and good picture of modern mathematics and its highlights. Here is the link to my slides.

In my case (but probably also for some other Bourbaki’s speakers) , it is not that I had full understanding (or close to it) of the proof and just had to decide how to present it, but my presentation largely represent what I know, and the seminaire forced me to learn. I was lucky that Peter gave a series of lectures (Video 1, Video 2, Video3Video4 ) about it in the winter at our Midrasha, and that he decided to write a paper “counting designs” based on the lectures, and even luckier that Jeff Kahn  taught some of it at class (based on Peter’s lectures and subsequent article) and later explained to me some core ingredients. Here is a link to Keevash’s full paper “The existence of design,” and an older post on his work.

Curiously the street was named only after Pierre Curie until the 60s and near the sign of the street you can still see the older sign.

# In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 18-31

The 18th yearly school in mathematics is devoted this year to combinatorics. It will feature lecture series by Irit Dinur, Joel Hass, Peter Keevash, Alexandru Nica, Alexander Postnikov, Wojciech Samotij, and David Streurer and additional activities. As usual grants for local and travel expences are possible.

# Amazing: Peter Keevash Constructed General Steiner Systems and Designs

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 ${{q-i} \choose {r-i}}$ should divide $\lambda {{n-i} \choose {r-i}}$ for every $1 \le i \le r-1$.

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 .