Erdős–Faber–Lovász conjecture, proved for all sufficiently large n (Kang–Kelly–Kühn–Methuku–Osthus, 2021/2023)

Statement

Posed by Erdős, Faber, and Lovász at a party in Boulder, Colorado in September 1972 (Erdős called it one of his three favorite combinatorial problems; the reward eventually reached $500). Three equivalent formulations, for $n\in\mathbb N$:

- (Set-system form) If $A_1,\dots,A_n$ are sets of size $n$ such that every pair shares at most one element, then $\bigcup_i A_i$ can be colored with $n$ colors so that every $A_i$ contains all $n$ colors. - (Graph form) If $G$ is the union of $n$ cliques, each on at most $n$ vertices, such that every pair of cliques shares at most one vertex, then $\chi(G)\le n$. - (Hypergraph edge-coloring form — the one the 2021 proof works with) If $H$ is a linear hypergraph on $n$ vertices (any two edges of $H$ meet in at most one vertex), then its chromatic index $\chi'(H)$ — the minimum number of colors needed to color the edges so that any two edges sharing a vertex get different colors — is at most $n$.

Question: is $\chi'(H)\le n$ for *every* $n$-vertex linear hypergraph $H$, with no exceptions?

Facts

- Status: proved for all sufficiently large $n$, still open in general (small $n$). Kang, Kelly, Kühn, Methuku, and Osthus proved: *for every sufficiently large $n$, every linear hypergraph $H$ on $n$ vertices has $\chi'(H)\le n$* [arXiv:2101.04698, Theorem 1.1; published *Annals of Mathematics* 198 (2023), no. 2, 537–618]. The threshold $n_0$ is not made numerically explicit (it falls out of a tower of $\gg/\ll$-hierarchy constants used throughout the proof) — this is why the page is titled "asymptotically solved" rather than "solved": the conjecture for small/all $n$ remains formally open. - Three tight extremal examples, which any correct proof must handle as boundary cases: (1) the complete graph $K_n$ for odd $n$ (and minor modifications), bounded edge size 2; (2) a finite projective plane of order $k$ on $n=k^2+k+1$ points, edges of size $k+1\approx\sqrt n$ ("FPP-extremal"); (3) the degenerate plane $\{\{1,2\},\dots,\{1,n\},\{2,\dots,n\}\}$, one edge of size $n-1$. The coexistence of a bounded-edge-size extremal case and an unbounded-edge-size extremal case is exactly what makes the conjecture hard — no single-scale argument can cover both. - Pre-2021 progress ladder (all confirmed in the paper's Introduction and cross-confirmed on Wikipedia): - Chang & Lawler (1988): $\chi'(H)\le\lceil 3n/2-2\rceil$ for every $n$-vertex linear hypergraph. - Kahn & Seymour (1992): the *fractional* chromatic index is $\le n$ (exact, not asymptotic). - Seymour (1982... via [50]): every $n$-vertex linear hypergraph has a matching of size $\ge e(H)/n$ (this follows from EFL but was proved unconditionally, and is already hard). - Kahn (1992, [27]): the first genuinely asymptotic result, $\chi'(H)\le n+o(n)$, via the Rödl nibble (semi-random method). This is the direct ancestor the 2021 paper builds on and sharpens to an exact bound. - Faber & Harris (2020): proved the conjecture outright for hypergraphs whose edge sizes all lie in $[3,\,c\sqrt n]$ for a small constant $c>0$ — i.e. resolved the "small/medium edges only" sub-case, but not edges near or above $\sqrt n$ scale. - Pippenger–Spencer (also Rödl-nibble-based): $\chi'(H)\le D+o(D)$ for uniform hypergraphs of max degree $D$ and codegree $o(D)$ — implies EFL for large *bounded-uniformity* ($r\ge3$ fixed) linear hypergraphs, a special case. - What "sufficiently large $n$" bought beyond exactness: the same paper proves two stability theorems (1.2, 1.3) confirming a prediction of Kahn — if $H$ is "far" from the extremal examples (bounded max degree away from $n$, not concentrated near the FPP edge-size $\sqrt n$), the true bound is much better than $n$: $\chi'(H)\le(1-\sigma)n$ or even $\le\varepsilon n$ for any $\varepsilon>0$ once $H$ is far enough from *all* extremal shapes. This says the worst case is genuinely isolated to a thin neighborhood of three rigid combinatorial structures. - Algorithmic version: the proof of Theorem 1.1 can be turned into a randomized polynomial-time coloring algorithm (Kang–Kelly–Kühn–Methuku–Osthus, companion paper [34], "algorithmic aspects," IEEE conference publication) — the semi-random/nibble machinery is constructive, not just existential. - Listed as Erdős Problem #19 on erdosproblems.com (search-engine-corroborated; the site returned HTTP 403 on direct fetch during this research, so treat the exact number as high-confidence but not primary-source-verified here). - Immediately after finishing this proof, the same authors reused Sections 5–6 of the machinery to solve a separate Erdős problem on coloring cliques that overlap in a bounded number of vertices [ref [35] in the paper], and Kelly–Kühn–Osthus reused the nibble argument to get asymptotically tight list-chromatic-number bounds for unions of nearly-disjoint bounded-degree graphs (confirming a case of a conjecture of Vu) — direct evidence the technique below is portable, not a one-off trick.

Solution

Answer: YES for all sufficiently large $n$ — every $n$-vertex linear hypergraph has chromatic index at most $n$, once $n$ exceeds an (ineffective) threshold $n_0$.

The transferable idea — a four-part pipeline for edge-coloring linear hypergraphs near a tight extremal bound. The proof does not use one trick; it *combines* four ingredients, each individually well-known, in a specific architecture that is the real export:

1. Scale-decompose the edges, and characterize the extremal cases first. Partition $H$'s edges by size relative to $n$: small ($\le r_1$, a large constant), medium, large, and "FPP-extremal" ($\approx\sqrt n$, the finite-projective-plane danger zone), plus "huge" ($\ge\beta n/4$). This is not cosmetic — the two hard extremal examples ($K_n$ and the projective plane) sit at *opposite* ends of this scale (edge size 2 vs. edge size $\sqrt n$), so no uniform argument can see both; the proof runs a genuinely different sub-argument in each regime and only unifies them at the very end via a shared color budget. Reusable move: when an extremal problem has multiple structurally unrelated tight examples, look for a *scale* (here, edge size) that separates them, solve each regime on its own terms, then glue via careful bookkeeping of a shared resource (here, the $n$ available colors, split into disjoint blocks $C_1,C_2,\dots$).

2. For small/bounded-size edges — the "nibble + reservoir-absorption + Vizing" engine (Section 2.1). This is the core reusable engine, worth stating on its own: - Reserve a random sub-piece $R$ of the graph part of $H$ (edges of size 2), each included independently with some probability, to be spent later as an "absorber." - Nibble the rest. Apply the Rödl nibble (semi-random/iterative-probabilistic matching construction — Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings) to $H\setminus R$ to build a sequence of large, pseudorandom matchings $N_i$; by the Pippenger–Spencer-type bound this alone gets you to *near*-optimal ($\chi'\approx n/2+o(n)$ in the worst sub-case), not exact. - Absorb the defects. The matchings $N_i$ from the nibble are pseudorandom enough that a controlled number of edges from the *reserved* set $R$ can be added to each $N_i$ to extend it into a matching $M_i$ that achieves "nearly-perfect coverage" (Definition 2.1: every high-degree vertex is covered by all but at most one color class) of the dangerous high-degree vertex set $U=\{u:\ d(u)\ge(1-\varepsilon)n\}$. This is a vertex-absorption argument (technique introduced by Rödl–Ruciński–Szemerédi for spanning-structure problems, first ported to *edge-decomposition* problems by the same authors' earlier solution of Kelly's conjecture on tournament decompositions) — $R$ plays the role of a flexible reservoir that can patch whichever few vertices the random process happened to miss. - Finish deterministically with Vizing. Once nearly-perfect coverage of $U$ is achieved, the *maximum degree of the leftover graph* $H\setminus H'$ is provably $\le n-|C|$ for the color set $C$ already used — small enough that Vizing's theorem ($\chi'(G)\le\Delta(G)+1$, or $\le\Delta(G)$ under a two-vertices-of-max-degree condition) finishes the leftover graph exactly, with no further randomness. Reusable move: randomized/semi-random methods (nibble) get you a near-optimal *fractional* or *approximate* structure fast; a reserved-randomness *absorber* patches the O(1)-fraction of "bad" defects a pure nibble leaves behind; a classical *exact* deterministic theorem (Vizing here) cleans up the final small-max-degree remainder. This "nibble → absorb → exact cleanup" three-stage pipeline is the single most portable idea on this page — it generalizes to any decomposition/coloring problem where (a) a semi-random method gets you within $o(n)$ of the target, (b) the defects are structured enough to be absorbable by a reserved random subset, and (c) a sharp classical theorem exists for the resulting near-regular leftover. - A genuinely non-full hypergraph (not "$(\rho,\varepsilon)$-full", Definition 2.2 — i.e. not too close to $K_n$) admits this whole pipeline outright; the $(\rho,\varepsilon)$-full case (structurally close to $K_n$) instead routes the leftover graph through a quasirandom-regular-graph decomposition result (Csaba–Kühn–Lo–Osthus–Treglown's resolution of the overfull-subgraph conjecture, itself a consequence of the Hamilton-decomposition/robust-expander machinery of Kühn–Osthus) rather than raw Vizing — i.e. when the leftover isn't just low-degree but *forced to be graph-theoretically rigid* (near-$K_n$), swap the classical cleanup theorem for a sharper one tailored to that rigidity.

3. For large/FPP-extremal edges — reordering + local sparsity (Section 2.2). Work with the line graph $L(H)$ (so $\chi'(H)=\chi(L(H))$, converting hypergraph edge-coloring into ordinary graph vertex-coloring). Greedily color edges in decreasing size order; the greedy bound is $\chi'(H)\le\max_i d_H^{\preceq}(e_i)+1$ where $d^\preceq$ counts earlier, intersecting edges. The key extra move (the Reordering Lemma, Lemma 6.2) is to allow the ordering to deviate from strict size-monotonicity: if the naive greedy bound is about to fail at some edge $e^*$, either the ordering can be locally rearranged to reduce the count, or there is a size-homogeneous block $W$ around $e^*$ covering almost all vertex pairs — and in the latter case $L(W)$ is provably locally sparse (a linearity consequence), so a Johansson/Molloy–Reed-type "locally sparse graphs color far below their max degree" bound applies to $W$, freeing up enough color budget to finish. Near the true FPP-extremal scale ($|e^*|\approx\sqrt n$), the argument switches again to a direct combinatorial trick: bound $e(H')\le(1+O(\delta))n$ by a double-counting/linearity argument, then find a matching in the *complement* of $L(H')$ of the right size and merge matched pairs into shared colors. Reusable move: when greedy-by-a-natural-order almost works but fails at isolated bad points, don't abandon greedy — first try to locally *reorder* around the failure, and only fall back to a heavier tool (local sparsity / locally-sparse coloring bounds) exactly at the points where reordering provably cannot help.

4. Glue the regimes via an explicit color-budget partition (Section 2.3). The two colorings (small-edge nibble-absorption-Vizing, large-edge reordering) are made *compatible* by partitioning the $n$ colors into disjoint labeled blocks in advance ($C_1$ for medium/large edges, $C_2$ for small edges, $C_\text{final}$ for the graph leftover, with sub-blocks $C_\text{huge}, C_\text{med}$, etc.) and proving each regime's argument only needs a bounded fraction of vertices' color-lists to be untouched by the other regime (properties (I)–(III) in the paper) — i.e. the two arguments are run almost independently and shown a-posteriori to not collide, rather than being interleaved. Reusable move: to combine two different regime-specific arguments into one global coloring/decomposition, pre-partition the shared resource (colors) into blocks sized in advance from the hierarchy of constants, and prove *cross-regime interference bounds* (each block only lightly touches the other regime's structure) rather than trying to jointly optimize both regimes at once.

Why this cracked a 50-year-old problem where Kahn's $n+o(n)$ stalled: Kahn's 1992 nibble alone gets an $o(n)$-additive error for free (nibble is inherently a "few percent defects" method), but closing that $o(n)$ gap to an *exact* $n$ requires handling the defects deterministically — which is exactly what the reservoir-absorption-Vizing addition supplies for small edges, and what the reordering-plus-local-sparsity refinement supplies for large edges. Neither half is new (nibble: Rödl 1985; absorption: Rödl–Ruciński–Szemerédi 2006; Vizing: 1964; locally-sparse coloring: Johansson/Kim 1990s) — the contribution is the specific *combination and scale-decomposition* that makes all of them meet exactly at budget $n$, plus the technical machinery (Ehard–Glock–Joos pseudorandom-matching theorem, Kahn's list-chromatic-index theorem, a Lovász $(g,f)$-factor argument) needed to make each piece rigorous at the correct error order.

Related

- Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the semi-random/iterative-probabilistic matching-construction method that is stage 1 of the core engine; also the direct ancestor of Kahn's 1992 $n+o(n)$ bound this paper sharpens to exact. - Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble / Semi-random nibble vs. probabilistic log-prime/discrete-log constructions: two routes to beating the greedy exponent — the general technique family this page's stage-1/stage-2 (nibble + absorption) belongs to; useful entry points for other open problems that need a "build most of the structure randomly, patch the rest" argument. - Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization) — related covering/matching machinery for linear hypergraphs (Seymour's matching bound, Kahn–Seymour fractional chromatic index) that forms the classical precursor results cited in Facts above. - erdos/19 — this conjecture's own entry in the Erdős-problems numbering (erdosproblems.com; not yet present as a page in this wiki — create as erdos/19 if/when a dedicated open-problem page is needed for the small-$n$/general case, which is still formally open). - Open generalizations this technique is a candidate for (not yet pages in this wiki, flagged for future linking): the Berge–Füredi generalization ($\chi'(H)\le\max_{v}|\bigcup_{e\ni v}e|$, a direct analogue of Vizing's theorem for linear hypergraphs — still open); the list-coloring strengthening of EFL first raised by Faber (still open); the Alon–Saks–Seymour conjecture on bipartite-graph edge-decompositions (a natural-looking generalization in the *same family* that was disproved in a strong form by Huang–Sudakov, an instructive cautionary case showing the "local density controls global chromatic number" heuristic is not universal even though it held for EFL). - concept/vizing-theorem — if/when created: the deterministic exact-coloring cleanup tool used as stage 3 of the core engine; a template for "what closes the gap after a semi-random method gets you to $o(n)$."