The Erdős-Faber-Lovász Conjecture: Fifty Exciting Years

Summary: Originally posed in 1972, the Erdős-Faber-Lovász conjecture became one of Erdős’ three favorite combinatorial problems. In 2021, five authors (Kang, Kelly, Kühn, Methuku, and Osthus) posted a preprint—eventually to appear as an (Formula presented.) -page article in the Annals of Mathematics (2023)—proving the conjecture for all sufficiently large values of its parameter. Though the intricate proof is beyond the reach of “ordinary” folks, the original problem’s simplicity makes it attractive to all, and early attacks showcased lots of exciting discrete mathematics. For example, Vizing’s theorem bounding a graph’s chromatic index appears, as does the de Bruijn-Erdős theorem on set systems with all pairwise intersections being singletons. This article offers a gentle introduction to the conjecture for nonspecialists.