Amazing: Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus give a new proof for Keevash’s Theorem. And more news on designs.

Blogging was slow recently, and I have various half written posts on all sort of interesting things, and plenty of unfulfilled promises. I want to quickly share with you two and a half news items regarding combinatorial designs. As you may remember Peter Keevash proved the century old conjecture on the existence of designs. We talked about it in this post, and again in this post. I wrote a Bourbaki exposition about this development and related results and problems. I gained some (rather incomplete) understanding of the proof by listening to Peter’s lectures, looking at the papers, talking to people, preparing to my lecture about it, writing the presentation, and  incorporating remarks of people who read earlier versions and pointed out that I miss some important ingredient.

The existence of designs – second proof!

A new proof for Keevash’s theorem on the existence of designs was discovered by  Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus! The proof is given in the paper  The existence of designs via iterative absorption, and the paper contains also some new applications of the method of proof. This is great news! A second proof to a major difficult theorem is always very very important and exciting.  Keevash’s theorem gave a vast generalization of the problem for decompositions of hypergraphs to complete subhypergraphs  and the new theorem is even a much more general hypergraph decomposition theorem. Congratulations!

New q-analogs of designs

One of the important open problems about designs is the existence of q-analogs. The first example was given in 1987 by Simon Thomas. Michael  Braun, Tuvi Etzion , Patric R. J. Östergard , Alexander Vardy,  and Alferd Wasserman found  remarkable new q-designs. See also this article: Researchers found mathematical structure that was thought not to exist.  Congratulations! It is an interesting question if the new existence methods apply to q-analogs (and perhaps in greater generality for all sort of algebraic gadgets).

Some more things

As part of a project with Nati Linial and Yuval Peled I was interested in finding a k-dimensional simplicial complex on k(k-1) vertices with a complete (k-1)-dimensional skeleton, with vanishing rational homology so that every (k-1) face is included in the same number of k-faces. (This “same number” must be k.) Better still I want all links of i-faces to be combinatorially the same. For k=2 the 6-vertex triangulation of  \mathbb R P^2  is an example, but I did not have any other example. I asked about it on MathOverflow and  GNiklasch identified a remarkable example for k=3. (And there are some hopes for k=4.) Actually, I need to devote a post to MathOverflow experiences. I got answers there to several problems that intrigued me for decades.

One more thing: Daniela Kühn and Deryk Osthus were involved in recent years (sometimes with coauthors) in knocking out some very important problems in graph theory and extremal combinatorics. Their ICM14 survey describes some of their works related to Hamiltonian cycles including their solution to the famous Kelly’s conjecture.

This entry was posted in Combinatorics, Updates and tagged , , , , , , , , . Bookmark the permalink.

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