Worked solution: Kang–Kelly–Kühn–Methuku–Osthus asymptotic proof via iterative absorption (2021)

Frequently asked questions

Why is going from "

n+o(n)

" to exactly "

n

" so much harder than the earlier improvements?

Because the $o(n)$ slack in Kahn's bound is exactly the room needed to patch up the small number of tricky, near-extremal hypergraphs (like odd complete graphs or near-projective-planes); removing that slack means finding an entirely separate, delicate argument for precisely those hard cases, which the newer paper achieves via its stability theorem and case analysis by edge size.

Source

Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus, 2021

A proof of the Erdős–Faber–Lovász conjecture

arXiv:2101.04698v1

Condensed summary

Step 2 of 8: Five decades of partial progress before the full proof

Previous step Next step

In plain words

Long before anyone could prove the exact bound of $n$ colours, mathematicians chipped away at weaker versions: first showing roughly $1.5n$ colours always suffice, then -- via a powerful randomized "nibbling" technique -- showing that $n$ colours suffice up to a vanishingly small error as $n$ grows. Getting from "almost $n$ " to "exactly $n$ " turned out to need entirely new ideas, since the small error term hides exactly the cases (like the tight examples) where every colour must be used with no slack at all.

\chi'(\mathcal{H}) \le n + o(n)

Detailed analysis

Kang, Kelly, Kuhn, Methuku and Osthus (2023, Section 1.1) survey the earlier progress. Seymour (proving a consequence of the conjecture) showed every $n$ -vertex linear hypergraph has a matching of size at least $e(\mathcal{H})/n$ . Chang and Lawler (1988) proved the bound $\chi'(\mathcal{H}) \le \lceil 3n/2-2\rceil$ directly. The real breakthrough was Kahn (1992), who used the Rodl nibble -- an iterative random-matching construction originally developed by Rodl to prove the Erdos-Hanani conjecture on combinatorial designs -- to prove the asymptotic bound $\chi'(\mathcal{H}) \le n + o(n)$ ; this built on the closely related Pippenger-Spencer theorem, which shows any hypergraph of maximum degree $D$ and small codegree has chromatic index $\chi'(\mathcal{H}) \le D + o(D)$ . Faber and Harris (2020) separately proved the exact bound for hypergraphs whose edges all have size between $3$ and $cn^{1/2}$ , for a small constant $c>0$ .

Terms in this step

Rödl nibble: An iterative probabilistic technique that builds a large matching (or colouring) by repeatedly taking a small random "nibble" of edges, removing them, and repeating on what remains, so the structure accumulates gradually while staying under control.
Codegree: For two vertices $u,v$ , the number of hyperedges containing both; "small codegree" means no two vertices share too many edges, a technical condition needed for nibble-type arguments.

Knowledge used in this step

The probabilistic method