To cheer you up in difficult times 17: Amazing! The Erdős-Faber-Lovász conjecture (for large n) was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus!

Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus have just uploaded a paper to the arXive, A proof of the Erdős-Faber-Lovász conjecture. (I am thankful to Nati Linial and Ryan Alweiss for telling me about it.)

Here is one formulation of the conjecture:

Erdős-Faber-Lovász Conjecture: Let F be a family of k-subsets of \{1,2,\dots,n\}. Suppose that every two sets in F have at most one element in common, then F can be divided into at most n families so that every two sets in each of these families are disjoint.

Using some standard hypergraph jargon the conjecture can be stated as follows:

Erdős-Faber-Lovász Conjecture: The chromatic index of any linear hypergraph on n vertices is at most n.

Here a linear hypergraph is a hypergraph where every two edges share at most one vertex. The chromatic index of a hypergraph is the number of colors needed to color the edges so that  every two intersecting edges have distinct colors.

The new result asserts

Theorem  (Kang, Kelly, Kühn, Methuku, and Osthus): For every sufficiently large n, every linear hypergraph H on n vertices has chromatic index at most n.

A stability versions of this result, which confirm a prediction of Jeff Kahn, is also provided. Of course, it will be interesting to settle the conjecture for all values of n.

This is an amazing breakthrough! Congratulations!

(from Wikipedea)

 

Daniella Kühn, Deryk Osthus, Tom Kelly, and Abhishek Methuku  (I will add a picture of Dong Yeap Kang when I will find Update: found! see below.)

A little more

Background and links: Here is the Wikipedea article. We mentioned the conjecture in this post and this one.

Matching and Fractional version. In 1982 Paul Seymour proved that any linear hypergraph H has a matching of size e(H)/n. In 1992 Jeff Kahn and Paul Seymour proved that the fractional chromatic index of any linear hypergraph on n vertices is at most n.

Approximate version via the semi random method. In 1992 Jeff Kahn proved that chromatic index of any linear hypergraph on n vertices is at most n(1+o(1)). Kahn used the Rödl nibble (aka semi-random) method. Kahn extended the result to list-coloring.

Open problems

There are many related open questions and some are mentioned in the paper. It will be interesting to prove EFL conjecture for all values of n. EFL-conjecture extends to  beautiful generalization of Vizing’s theorem which is still open. Also the EFL-conjecture for list coloring is still open. See also this 1994 article by Jeff Kahn on Hypergraphs matching, covering and coloring problems.

Another interesting problem is:

The restricted Larman’s conjecture: Let F be an intersecting family of k-subsets of \{1,2,\dots,n\}.  Then F can be divided into at most n 2-intersecting families, namely so that every two sets in each of these families have at least 2 elements in common.

Little Update: A few more details on the last problem. As far as I know for the restricted Larman conjecture it is not even known that F can always be divided into (1+o(1)) 2-intersecting families.

Now, call G strongly 2-intersecting if the intersection of all sets in G has at least two elements.  Furedi and Seymour proved that F can be fractionally covered by n strongly 2-intersecting subfamilies. They conjectured that F can always be covered by n strongly 2-intersecting families, however Jeff Kahn and I disproved this conjecture.

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

4 Responses to To cheer you up in difficult times 17: Amazing! The Erdős-Faber-Lovász conjecture (for large n) was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus!

  1. Gil Kalai says:

    I added some more details on the restricted Larman conjecture which has a similar flavour to the EFL conjecture at the end of the post.

  2. Pingback: Science Advisor | Gödel's Lost Letter and P=NP

  3. Pingback: Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson | Combinatorics and more

  4. Pingback: Closing an Erdős Problem | Gödel's Lost Letter and P=NP

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s