Proof of `Weak coloring numbers are bounded by strong coloring numbers`

groundedproofs/Lax12Proofs/WeakColoringBound.lean · lax-12

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.

Read the Lean proof on GitHub

Description

The weak rr-coloring number of a graph is at most 1+r(scolr1)r1 + r * (scol_r - 1) ^ r, where scolrscol_r is its strong rr-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 scolGrscol G r 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 scolscol under that order is at most scolGrscol G r; 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 wcolwcol, 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 Lax12Proofs.OrderedParameterBounds.wcolleofscolLax12Proofs.OrderedParameterBounds.wcol_le_of_scol.