A proof of the Erdos-Faber-Lovasz conjecture

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.