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

Step 6 of 8: Stitching the layers together without wasting colours

In plain words

If we used a brand-new palette of colours for the large edges, another palette for the medium edges, and a third palette for the small edges, the total number of colours would easily exceed $n$ . Instead, each colour class must be reused across layers: a colour first assigned to a large or medium hyperedge is later extended by adding disjoint small edges on the remaining vertices.

The challenge is that large and medium edges already block out sets of vertices inside each colour class, so the nibble-and-absorption machinery on the small edges must work inside whatever vertex subsets are still left free in each colour.

\mathcal{H}_1 \supseteq \mathcal{H}_{\text{large}},\quad \chi'(\mathcal{H}_1) \le |C_1|,\quad \text{extend colour classes via Rödl nibble to } \mathcal{H}_{\text{small}}

Detailed analysis

Kang, Kelly, Kühn, Methuku and Osthus (2023, Sections 2.2 and 7) explain how the colourings of the layers are combined. First, Section 5 colours all edges around or above the projective-plane scale $\sqrt{n}$ , producing a partial colouring with colour set $C_1$ . Next, Section 6 colours the medium edges using locally sparse graph colouring while carefully reusing colours from $C_1$ and introducing controlled new colours $C_2$ , ensuring that every high-degree vertex of $\mathcal{H}$ is covered by almost all colour classes used so far.

Finally, Section 7 extends these existing matchings (colour classes) into the small-edge subhypergraph $\mathcal{H}_{\text{small}}$ via a list-/matching-extension version of the Rödl nibble and reservoir absorption (building on Steps 3 and 4), so that heavy vertices in $U$ continue to have nearly-perfect coverage and the leftover size- $2$ edges can still be finished off by Vizing's theorem or $1$ -factorisation.

Terms in this step

Nearly-perfect coverage of $U$: A family of edge-disjoint matchings $\mathcal{N}$ has nearly-perfect coverage of the high-degree vertex set $U$ if every $u \in U$ is covered by at least $|\mathcal{N}|-1$ matchings and each matching misses at most one vertex of $U$ .

Knowledge used in this step

Graph coloring and the four color theorem The probabilistic method