Tag Archives: peter keevash

The existence of designs

The big news in combinatorics is this new preprint by Peter Keevash, which proves the existence of Steiner systems, or more generally combinatorial designs, for essentially every system of parameters where the existence of such a design isn’t ruled out on divisibility grounds.  Remarkable!

I’m not going to say anything about this paper except to point out that it has even more in it than is contained in the top-billed theorem; the paper rests on the probabilistic method, which in this case means, more or less, that Keevash shows that you can choose a “partial combinatorial design” in an essentially random way, and with very high probability it will still be “close enough” that by very careful modifications (or, as Keevash says, “various applications of the nibble” — I love the names combinatorists give their techniques) you can get all the way to the desired combinatorial design.

This kind of argument is very robust!  For instance, Keevash gets the following result, which in a way I find just as handsome as the result on designs.  Take a random graph on n vertices — that is, each edge is present with probability 1/2, all edges independent.  Does that graph have a decomposition into disjoint triangles?  Well, probably not, right?  Because a union of triangles has to have even degree at each vertex, while the random graph is going to have n/2 of its vertices with odd degree. (This is the kind of divisibility obstruction I mentioned in the first paragraph.)  In fact, this divisibility argument shows that if the graph can be decomposed as a union of triangles with M extra edges, M has to be at least n/4 with high probability, since that’s how many edges you would need just to dispose of the odd-degree vertices.  And what Keevash’s theorem shows is there really is (with high probability) a union of disjoint triangles that leaves only (1+o(1))(n/4) edges of the random graph uncovered!

More details elsewhere from Vuhavan and Gil Kalai.

Tagged , ,
%d bloggers like this: