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.

Read the Lean proof on GitHub

Description

Every nowhere dense graph class has subpolynomial density: for every depth rr and every ε>0ε > 0 there is a constant cc such that every depth-rr minor of a member, on mm vertices, has at most cm(1+ε)c * m^(1+ε) edges.

Proof strategy

The internal development proves the threshold form of the theorem — fewer than m(1+ε)m^(1+ε) edges once mm is at least a bound NN 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 Set.ncardcoefinsetSet.ncard_coe_finset.

Threshold form to constant form: take c=max1(N2)c = max 1 (N^2). Above the threshold the internal bound already gives <m(1+ε)cm(1+ε)< m^(1+ε) ≤ c * m^(1+ε); below it, a graph on mm vertices has at most m2N2cm^2 ≤ N^2 ≤ c edges while m(1+ε)1m^(1+ε) ≥ 1; and at m=0m = 0 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 Lax12Proofs.DensityOfShallowMinors.ndsubpolynomialdensityLax12Proofs.DensityOfShallowMinors.nd_subpolynomial_density.