Proof of `Strong coloring numbers are bounded by admissibility`
groundedproofs/Lax12Proofs/StrongColoringBound.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.
Description
The strong -coloring number of a graph is at most , where is its -admissibility.
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 , order the vertices by their positions under it, and observe two inclusions. First, every admissible family of paths in the internal sense is an admissible family of walks in the submitted sense, so the internal admissibility under that order is at most . Second, every vertex strongly reachable in the submitted sense is strongly 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 admissibility, which closes the chain.
Attribution
The statement is Lemma 2.5 of Chapter 2 of the sparsity lecture notes of Pilipczuk and Siebertz (numbering of the 2019/20 edition). The internal per-order version is .