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 , ,

5 thoughts on “The existence of designs

  1. Projective planes are a kind of design, no? Does this paper resolve the question of non-existence of finite projective planes of non-prime power order? I guess not, otherwise this would be front and center in the announcements. What am I missing?

  2. JSE says:

    Peter’s thing is for n sufficiently large relative to q and r; for a projective plane, you need both q and n growing so I think it’s still not known. (Someone correct me if I’m wrong here.) Indeed, if his methods could prove anything about projective planes, I think it would be that they DID exist!

  3. NDE says:

    Finite projective planes are surely beyond the range of this result because must satisfy a number-theoretic condition that goes beyond elementary congruences (if q is 2 mod 4 then q is the sum of two squares).

  4. […] 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. […]

  5. […] other blog post on this achievement: Van Vu,  Jordan Ellenberg, The […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 553 other followers

%d bloggers like this: