Proof of `Nowhere dense classes are uniformly quasi-wide`

groundedproofs/Lax12Proofs/NowhereDenseUQW.lean · lax-12

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.

Read the Lean proof on GitHub

Description

Every nowhere dense graph class is uniformly quasi-wide: for every radius rr there are a threshold function NN and a separator bound ss such that in every member, every vertex set of size at least NmN m contains a distance-rr independent subset of size at least mm after deleting at most ss vertices.

Proof strategy

The internal development proves the statement for classes indexed by arbitrary finite vertex types. The submitted class CC is therefore closed under subgraph copies — the closure is nowhere dense in the internal sense as soon as CC is nowhere dense in the submitted sense, since a internal minor model of a clique in a copy pushes forward to a submitted minor model in the host — the internal theorem is applied to the closure, and the conclusion is specialized back to the members of CC themselves. What remains is packaging: the internal statement is phrased with FinsetFinset and cardcard, the submitted one with SetSet and Set.ncardSet.ncard, and the two are matched by Set.toFinsetSet.toFinset and Set.ncardcoefinsetSet.ncard_coe_finset. Distance independence and vertex deletion need no translation at all: the internal step-reduction modules are stated over the definitions of the submitted concept.

The internal induction alternates an odd and an even distance-reduction step and consumes Ramsey's theorem twice — directly, to extract a homogeneous set, and through the bipartite Ramsey lemma (Lemma 3.9 of the notes) — so both Ramsey statements of the finiteramseyfinite-ramsey submission are assumed rather than reproved here.

Attribution

The statement is Lemma 3.4 of Chapter 4 of the sparsity lecture notes of Pilipczuk and Siebertz (numbering of the 2019/20 edition), the hard direction of their Theorem 3.2. The internal type-polymorphic version is Lax12Proofs.QuasiWidenessInduction.ndimpliesuqwLax12Proofs.QuasiWidenessInduction.nd_implies_uqw.