MathLabs

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

Step 7 of 8: Kahn's stability prediction: far from extremal means fewer colours
In plain words

Only three very rigid shapes actually force all nn colours: the odd complete graph KnK_n (all edges of size 22 and maximum vertex degree n−1n-1), the finite projective plane (around nn edges all of size near n\sqrt{n}), and the degenerate near-pencil (one vertex of degree n−1n-1 or one edge of size n−1n-1).

Kahn predicted that any linear hypergraph H\mathcal{H} that stays bounded away from both maximum degree nn and the projective-plane edge-size profile should need strictly fewer than nn colours -- and the authors' proof establishes this stability theorem along the way.

Δ(H)≤(1−δ)n and ∣{e∈H:∣e∣=(1±δ)n}∣≤(1−3δ)n  ⟹  χ′(H)≤(1−σ)n\Delta(\mathcal{H}) \le (1-\delta)n \text{ and } |\{e \in \mathcal{H} : |e| = (1\pm\delta)\sqrt{n}\}| \le (1-3\delta)n \implies \chi'(\mathcal{H}) \le (1-\sigma)n
Detailed analysis

Kang, Kelly, Kühn, Methuku and Osthus (2023, Section 1.2, Theorems 1.2 and 1.3) prove a quantitative stability result confirming Kahn's prediction. Theorem 1.2 states that for every δ>0\delta > 0, there exist n0,σ>0n_0, \sigma > 0 such that for n≥n0n \ge n_0, any nn-vertex linear hypergraph H\mathcal{H} with maximum degree Δ(H)≤(1−δ)n\Delta(\mathcal{H}) \le (1-\delta)n and at most (1−3δ)n(1-3\delta)n edges of size (1±δ)n(1\pm\delta)\sqrt{n} satisfies χ′(H)≤(1−σ)n\chi'(\mathcal{H}) \le (1-\sigma)n.

In fact, stability is not merely a bonus corollary: inside the main proof, whenever H\mathcal{H} is far from the finite projective plane (handled in Section 5) and has no vertices of degree close to nn (handled by absorption and 11-factorisation in Sections 4 and 7), the slack (1−σ)n(1-\sigma)n is precisely what gives the nibble and locally sparse colouring steps enough breathing room to finish without running out of colours.

Terms in this step
Finite projective plane (FPP)
A linear hypergraph on n=k2+k+1n = k^2+k+1 vertices with nn edges (lines) each of size k+1k+1, where every two vertices lie on a unique line and every two lines meet at a unique vertex, forcing χ′(H)=n\chi'(\mathcal{H}) = n.
Knowledge used in this step