Proof of `Nowhere dense classes have subpolynomial weak coloring numbers`
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Every nowhere dense graph class has subpolynomial weak coloring numbers: for every radius and every there is a constant such that every subgraph of a member, on vertices, satisfies .
Proof strategy
This is a glue proof: it assumes the four preceding statements of the submission and does nothing but compose them, so the proof network is visible on the archive rather than buried inside a single derivation.
Fix and , and set . Subpolynomial density, applied to the closure of the class under subgraph copies — which is nowhere dense whenever the class is — gives a constant bounding the edges of every depth- minor of a subgraph of a member by in its own vertex count . Since a shallow minor has no more vertices than its host, , so that bound rewrites as the per-graph density bound for : . A depth- topological minor is in particular a depth- minor, so bounds the topological density as well, and the admissibility bound yields ; admissibility is monotone in the radius, so the same bound holds at radius . The two coloring-number links then give — the arithmetic of Corollary 2.7 of the notes, which has no concept of its own.
What remains is real arithmetic. From and one gets , so with , using . The degenerate case is separate: there and .
Attribution
The statement is Theorem 3.4 of Chapter 2 of the sparsity lecture notes of Pilipczuk and Siebertz (numbering of the 2019/20 edition). The composition reproduces that derivation at the level of the submitted concepts.