Proof of `Nowhere dense classes have almost linear neighborhood complexity`

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

Nowhere dense graph classes have almost linear neighborhood complexity: the radius-1 case of the theorem of Eickmeyer, Giannopoulou, Kreutzer, Kwon, Pilipczuk, Rabinovich, Siebertz.

Proof strategy

Radius-1 specialization of the generalized-coloring-number route: a nowhere dense class is K_{t,t}-free, so its neighborhood set systems have VC dimension O(t + log t); Dvořák's densification bounds the depth-1 grad by f(ε)·n^ε, which bounds the weak 2-coloring number; counting neighborhood traces along a weak coloring order then yields |A| · n^ε traces, and localization to a polynomially small witness set rescales this to c · |A|^(1+ε). The weak-coloring input is the assumed statement Lax12.NowhereDenseWcol.hasSubpolynomialWcolofnowhereDenseLax12.NowhereDenseWcol.hasSubpolynomialWcol_of_nowhereDense.

Attribution

The statement is the radius-1 case of the theorem of Eickmeyer, Giannopoulou, Kreutzer, Kwon, Pilipczuk, Rabinovich and Siebertz, Neighborhood complexity and kernelization for nowhere dense classes of graphs; the source lecture notes discuss neighborhood complexity but cite the almost-linear bound as a result of the literature. The proof carried out here is Corollary 6b of Dreier, Mählmann, McCarty, Pilipczuk, Toruńczyk, which specializes the coloring-number route of the lecture notes (chapters 1, 2, 5) to radius 1; densification following Dvořák.