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

Frequently asked questions

Why is the bound

n+1

here, one more than the target

n

This warm-up argument is intentionally not tight: it is a simplified sketch showing the nibble-plus-absorption-plus-Vizing strategy works at all, and the extra $+1$ comes from Vizing's theorem's own $+1$ slack; removing it (Step 4) requires a separate, more delicate argument that only applies away from near-extremal hypergraphs.

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 3 of 8: Warm-up: reaching

n+1

colours via a random vertex-absorber

Previous step Next step

In plain words

Focus first on the easier case where every hyperedge has bounded size (say at most $r$ vertices), which turns most of $\mathcal{H}$ into an ordinary graph $G$ of size- $2$ edges. The idea is to set aside half of $G$ 's edges at random as a flexible "reservoir", colour everything else efficiently using the nibble, and then use the reservoir to patch up the handful of vertices -- especially those with very high degree, close to $n$ -- that the nibble alone could not perfectly cover.

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

Detailed analysis

Kang, Kelly, Kuhn, Methuku and Osthus (2023, Section 2.1) sketch the argument for bounded edge sizes $2 \le |e| \le r$ . Let $G$ be the graph of size- $2$ edges of $\mathcal{H}$ . Put each edge of $G$ into a random reservoir $R$ independently with probability $1/2$ ; with high probability every vertex satisfies $d_R(v) = d_G(v)/2 \pm \xi n$ for a small $\xi$ , so $\Delta(\mathcal{H}\setminus R) \le (1/2+\xi)n$ , and the Pippenger-Spencer theorem gives $\chi'(\mathcal{H}\setminus R) \le (1/2+\gamma)n$ . Applying the Rodl nibble iteratively to $\mathcal{H}\setminus R$ builds large matchings that cover the near-full-degree vertex set $U$ "nearly perfectly", using edges of $R$ to patch the (at most one) vertex each matching misses; the small number of leftover uncoloured edges then have maximum degree at most $n-|C|$ for the set of colours $C$ used so far, so Vizing's theorem gives $\chi'(\mathcal{H}\setminus\mathcal{H}') \le \Delta(\mathcal{H}\setminus\mathcal{H}')+1$ , yielding $\chi'(\mathcal{H}) \le n+1$ in total.

Terms in this step

Vizing's theorem: For any ordinary graph $G$ of maximum degree $\Delta$ , the chromatic index is at most $\Delta+1$ ; used here as a cheap final patch for a small leftover graph.
Vertex-absorber: A reserved random set of edges (here, the reservoir $R$ ) kept aside precisely so it can be used later to fix up the small number of vertices that an earlier random construction failed to handle perfectly.

Knowledge used in this step

Graph coloring and the four color theorem The probabilistic method