A proof of the Erdos-Faber-Lovasz conjecture
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Graph and hypergraph colouring problems are central to combinatorics, with applications and connections to many other areas, such as geometry, algorithm design, and information theory. However, for hypergraphs even basic problems have turned out to be rather challenging: in particular, the famous Erd˝os-Faber-Lov´asz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. (Here the chromatic index of a hypergraph H is the smallest number of colours needed to colour the edges of H so that any two edges that share a vertex have different colours.) There are also several other equivalent (dual) versions of this conjecture, e.g. in terms of colouring the vertices of nearly disjoint cliques. Erd˝os considered this to be one of his three most favorite combinatorial problems and offered $500 for the solution of the problem. In joint work with Dong-yeap Kang, Tom Kelly, Abhishek Methuku and Deryk Osthus, we prove this conjecture for every large n. We also provide ‘stability versions’ of this result, which confirm a prediction of Kahn. In my talk, I will discuss some background, some of the ideas behind the proof as well as some related open problems.
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !