Worked solution: Kang–Kelly–Kühn–Methuku–Osthus asymptotic proof via iterative absorption (2021)
Only three very rigid shapes actually force all colours: the odd complete graph (all edges of size and maximum vertex degree ), the finite projective plane (around edges all of size near ), and the degenerate near-pencil (one vertex of degree or one edge of size ).
Kahn predicted that any linear hypergraph that stays bounded away from both maximum degree and the projective-plane edge-size profile should need strictly fewer than colours -- and the authors' proof establishes this stability theorem along the way.
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 , there exist such that for , any -vertex linear hypergraph with maximum degree and at most edges of size satisfies .
In fact, stability is not merely a bonus corollary: inside the main proof, whenever is far from the finite projective plane (handled in Section 5) and has no vertices of degree close to (handled by absorption and -factorisation in Sections 4 and 7), the slack is precisely what gives the nibble and locally sparse colouring steps enough breathing room to finish without running out of colours.
- Finite projective plane (FPP)
- A linear hypergraph on vertices with edges (lines) each of size , where every two vertices lie on a unique line and every two lines meet at a unique vertex, forcing .