Worked solution: Kang–Kelly–Kühn–Methuku–Osthus asymptotic proof via iterative absorption (2021)
In a general linear hypergraph , hyperedges can have any size from up to : a projective plane has edges of size around , while a near-pencil has one giant edge of size . 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 into size regimes -- very large edges, edges near the projective-plane scale , 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 colours are still available.
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 intersect; instead, it bounds the number of pairwise disjoint such edges by . The proof isolates highly intersecting large-edge configurations, especially those near the finite-projective-plane scale , and uses their structure and stability to colour intersecting edges with distinct colours.
- Line graph
- The ordinary graph whose vertices are the hyperedges of , with two hyperedges joined by an edge in whenever they share a vertex in ; edge-colouring is the same as vertex-colouring .
- Locally sparse graph
- A graph of maximum degree in which the neighbourhood of every vertex spans relatively few edges; Johansson-type theorems show such graphs can be coloured with colours, far fewer than the trivial .