The year in proofs has started with a big result in combinatorics: the existence conjecture for designs. As usual, weightier minds than ours have comprehensively explained the result, so I’ll just give a brief summary of the problem and then some links.

A Steiner system generalises Thomas Kirkman’s “schoolgirl problem”:

Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.

Now, generalise all the numbers in that problem: suppose you’ve got a set $X$ of $n$ elements. Does there exist a collection $S$ of subsets of $X$, each with $q$ elements, so that every possible subset of $X$ with $r$ elements appears in exactly one member of $S$? Such a set $S$ is called a Steiner system with parameters $(n,q,r)$. More generally, you can ask that each $r$-subset appears in exactly $\lambda$ elements of $S$, instead of just one – that’s called a design, because people got into looking for them while designing experiments.

It was very quickly proved that in order for a design $(n,q,r,\lambda )$ to exist, $(\genfrac{}{}{0ex}{}{q-i}{r-i})$ has to divide $\lambda (\genfrac{}{}{0ex}{}{n-i}{r-i})$ for every $0\le i\le r-1$. That’s a necessary condition, but it was also conjectured that it’s sufficient – if $(n,q,r,\lambda )$ satisfies the divisibility condition, then a design with those parameters exists.

Peter Keevash of Oxford University gave a short twenty-minute talk at Oberwolfach at the start of the month where he announced a proof of the conjecture. The proof uses a new variant of the probabilistic method – a technique he calls Randomized Algebraic Construction.

I hope that’s whetted your appetite. Van Vu wrote a very short blog post explaining the problem and the proof technique based on a conversation with Keevash; Gil Kalai has restated the problem and given a potted history; and Jordan Ellenberg has been very enthusiastic about the further applications of Keevash’s method.

More information

The paper: The existence of designs by Peter Keevash on the arXiv.
Peter Keevash’s homepage.
Big News: Existence of designs by Van Vu.
Amazing: Peter Keevash Constructed General Steiner Systems and Designs by Gil Kalai.
The existence of designs by Jordan Ellenberg.

via Ben Green on Google+