Coloring hypergraphs of small codegree, and a proof of the Erdős–Faber–Lovász conjecture

Job Candidate Talk
Thursday, January 20, 2022 - 11:00am for 1 hour (actually 50 minutes)
Thomas Kelly – University of Birmingham –
Anton Bernshteyn

Meeting link:

A long-standing problem in the field of graph coloring is the Erdős–Faber–Lovász conjecture (posed in 1972), which states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$, or equivalently, that a nearly disjoint union of $n$ complete graphs on at most $n$ vertices has chromatic number at most $n$.  In joint work with Dong Yeap Kang, Daniela Kühn, Abhishek Methuku, and Deryk Osthus, we proved this conjecture for every sufficiently large $n$.  Recently, we also solved a related problem of Erdős from 1977 on the chromatic index of hypergraphs of small codegree.  In this talk, I will survey the history behind these results and discuss some aspects of the proofs.