Proof of `Nowhere dense classes are uniformly quasi-wide`
What this proof establishes
- thm✓
Lax14.MulticolorRamsey - thm✓
Lax14.Ramsey
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 is uniformly quasi-wide: for every radius there are a threshold function and a separator bound such that in every member, every vertex set of size at least contains a distance- independent subset of size at least after deleting at most vertices.
Proof strategy
The internal development proves the statement for classes indexed by arbitrary finite vertex types. The submitted class is therefore closed under subgraph copies — the closure is nowhere dense in the internal sense as soon as 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 themselves. What remains is packaging: the internal statement is phrased with and , the submitted one with and , and the two are matched by and . 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 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 .