Proof of `Admissibility is bounded by topological shallow-minor density`

groundedproofs/Lax12Proofs/AdmissibilityBound.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

If every depth-rr topological minor of a graph GG has at most dd times as many edges as vertices, then the (r+1)(r+1)-admissibility of GG is at most 1+6(r+1)d31 + 6 * (r+1) * d ^ 3.

Proof strategy

The internal development proves exactly this statement, at radius r+1r + 1 with its hypothesis at depth (r+1)1=r(r + 1) - 1 = r, so the discharge is pure idiom translation and no weakening step is needed.

Two translations are involved. On the hypothesis side, the internal topological minor model routes each edge of the minor along a path, with a chosen tail and Sym2Sym2 plumbing, while the submitted model carries a walk for each adjacent pair; the repackaging orients an edge by its chosen tail and reverses the walk for the other orientation. The submitted density predicate ranges over minors on the canonical carriers FinmFin m only, so the arbitrary finite carrier of the internal hypothesis is transported along Fintype.equivFinFintype.equivFin and the edge counts are matched by Set.ncardSet.ncard-to-edgeFinsetedgeFinset and by invariance of the edge count under a graph isomorphism. On the conclusion side, the internal theorem produces a linear order; its rank permutation witnesses HasAdmAtMostHasAdmAtMost, because a submitted admissible family of walks bypasses to an internal admissible family of paths of the same size, and the submitted admadm — an infimum over permutations — is then bounded by Nat.sInfleNat.sInf_le.

Attribution

The statement is Lemma 3.2 of Chapter 2 of the sparsity lecture notes of Pilipczuk and Siebertz (numbering of the 2019/20 edition), with the radius index shifted by one. The internal per-order version is Lax12Proofs.AdmByDensity.admleoftopGradboundLax12Proofs.AdmByDensity.adm_le_of_topGrad_bound.