Proof of `Weak coloring numbers are bounded by strong coloring numbers`
What this proof establishes
no assumptions
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
The weak -coloring number of a graph is at most , where is its strong -coloring number.
Proof strategy
The internal development proves the inequality for a fixed linear order. The submitted parameters are minima over vertex permutations, so it is enough to run the internal bound under one well-chosen order: take a permutation witnessing and order the vertices by their positions under it. Every vertex strongly reachable in the internal sense is strongly reachable in the submitted sense — a path is a walk — so the internal under that order is at most ; and every vertex weakly reachable in the submitted sense is weakly reachable in the internal sense — a walk bypasses to a path with a smaller support — so the submitted , being the minimum over permutations, is at most the internal one. The right-hand side is monotone in the strong coloring number, which closes the chain.
Attribution
The statement is Lemma 2.6 of Chapter 2 of the sparsity lecture notes of Pilipczuk and Siebertz (numbering of the 2019/20 edition). The internal per-order version is .