Proof of `Nowhere dense classes have subpolynomial shallow-minor density`
groundedproofs/Lax12Proofs/NowhereDenseDensity.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
Every nowhere dense graph class has subpolynomial density: for every depth and every there is a constant such that every depth- minor of a member, on vertices, has at most edges.
Proof strategy
The internal development proves the threshold form of the theorem — fewer than edges once is at least a bound depending on the depth and on — for classes indexed by arbitrary finite vertex types. The submitted class is therefore closed under subgraph copies, whose internal nowhere denseness follows from the submitted one, and the internal theorem is instantiated at a submitted member, which lies in that closure. A submitted minor model becomes an internal one by bypassing its walks to paths, and the edge counts are matched by .
Threshold form to constant form: take . Above the threshold the internal bound already gives ; below it, a graph on vertices has at most edges while ; and at both sides vanish. This is the equivalence the notes themselves record immediately after the theorem.
Attribution
The statement is Theorem 3.1 of Chapter 1 of the sparsity lecture notes of Pilipczuk and Siebertz (numbering of the 2019/20 edition), whose presented proof is credited there to Zdeněk Dvořák. The internal threshold version is .