Erdős–Faber–Lovász conjecture

Solved, 2021Combinatorics and discrete mathematicsErdős

Statement

If $G = \bigcup_{i=1}^n A_i$ is the union of $n$ edge-disjoint complete graphs $A_1, \dots, A_n$ , each on $n$ vertices, such that $|V(A_i) \cap V(A_j)| \le 1$ for all $1 \le i < j \le n$ , then the chromatic number of $G$ satisfies $\chi(G) = n$ (equivalently, every linear hypergraph on $n$ vertices has chromatic index $\chi'(\mathcal{H}) \le n$ ).

Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus announced a proof in January 2021 (published in the Annals of Mathematics in 2023) establishing the Erdős–Faber–Lovász conjecture for all sufficiently large $n \ge n_0$ . Strictly speaking, the problem across all integers $n$ is solved asymptotically (for $n \ge n_0$ ) and verified for $n \le 12$ (Hindman 1981 for $n \le 10$ ; Romero and Alonso-Pecina 2014 for $n \le 12$ ), while finite intermediate values $13 \le n < n_0$ remain open.

Posed by, 1972Paul Erdős

In the dual hypergraph formulation, the Erdős–Faber–Lovász conjecture states that any linear hypergraph $\mathcal{H}$ on $n$ vertices can be edge-colored with $n$ colors. Equality $\chi'(\mathcal{H}) = n$ is achieved by three distinct extremal families: a single edge of size $n$ , a near-pencil (one edge of size $n - 1$ and $n - 1$ edges of size $2$ ), and a projective plane of order $k$ on $n = k^2 + k + 1$ points (together with degenerations). Kang, Kelly, Kühn, Methuku, and Osthus also proved Kahn's stability conjecture characterizing all linear hypergraphs with $\chi'(\mathcal{H}) = n - o(n)$ .

References

Neil Hindman (1981). On a conjecture of Erdős, Faber, and Lovász · DOI:10.1016/0097-3165(81)90016-9
Jeff Kahn (1992). Coloring the Meyniel hypergraph · DOI:10.1016/0097-3165(92)90068-6
Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, Deryk Osthus (2023). A proof of the Erdős-Faber-Lovász conjecture · DOI:10.4007/annals.2023.198.2.2 · arXiv:2101.04698

History of the problem

1972Paul Erdős, Vance Faber, and László Lovász formulate the conjecture at a tea party in Boulder, Colorado; Erdős initially expects it to be easy, but soon offers a USD $500$ prize for its resolution.Paul Erdős
1981Neil Hindman proves that for each fixed $n$ the conjecture reduces to finitely many hypergraphs and verifies it for all $n \le 10$ ; Paul D. Seymour (1982) proves that every $n$ -vertex linear hypergraph has a matching of size at least $m/n$ , where $m$ is the number of edges.
1992Jeff Kahn proves the asymptotic Erdős–Faber–Lovász conjecture $\chi'(\mathcal{H}) \le (1 + o(1))n$ for every $n$ -vertex linear hypergraph using the Rödl nibble method, earning a USD $100$ consolation prize from Erdős.
2021Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus prove the exact bound $\chi'(\mathcal{H}) \le n$ for all sufficiently large $n$ (published in the Annals of Mathematics in 2023) by combining structural extremal cases (near-projective planes and high-degree vertices) with random nibble and absorption.

Prizes

Paul Erdős prize, $500 — awarded