MathLabs

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

Step 5 of 8: Stratifying edges by size: large, medium, and small
In plain words

In a general linear hypergraph H\mathcal{H}, hyperedges can have any size from 22 up to nn: a projective plane has edges of size around n\sqrt{n}, while a near-pencil has one giant edge of size n−1n-1. No single colouring tool works across all scales, because two giant edges almost always collide at a shared vertex, whereas tiny edges rarely collide.

The authors therefore slice H\mathcal{H} into size regimes -- very large edges, edges near the projective-plane scale n\sqrt{n}, medium edges, and bounded-size small edges -- and colour them from largest down to smallest so that the hardest collisions are resolved first while all nn colours are still available.

H=Hsmall∪Hmed∪Hlarge,χ′(L(Hmed))=O(Δ/log⁡Δ)\mathcal{H} = \mathcal{H}_{\text{small}} \cup \mathcal{H}_{\text{med}} \cup \mathcal{H}_{\text{large}}, \quad \chi'(L(\mathcal{H}_{\text{med}})) = O(\Delta / \log \Delta)
Detailed analysis

Kang, Kelly, Kuhn, Methuku and Osthus (2023, Sections 2.2 and 5) partition the edges by size and treat the difficult large-edge configurations separately. Linearity does not make every pair of edges larger than n\sqrt{n} intersect; instead, it bounds the number of pairwise disjoint such edges by n\sqrt{n}. The proof isolates highly intersecting large-edge configurations, especially those near the finite-projective-plane scale (1±δ)n(1 \pm\delta)\sqrt{n}, and uses their structure and stability to colour intersecting edges with distinct colours.

Terms in this step
Line graph L(H)L(\mathcal{H})
The ordinary graph whose vertices are the hyperedges of H\mathcal{H}, with two hyperedges joined by an edge in L(H)L(\mathcal{H}) whenever they share a vertex in H\mathcal{H}; edge-colouring H\mathcal{H} is the same as vertex-colouring L(H)L(\mathcal{H}).
Locally sparse graph
A graph of maximum degree Δ\Delta in which the neighbourhood of every vertex spans relatively few edges; Johansson-type theorems show such graphs can be coloured with O(Δ/log⁡Δ)O(\Delta / \log \Delta) colours, far fewer than the trivial Δ+1\Delta + 1.
Knowledge used in this step