Lax

Draft — mutable and not usable as a dependency; its citation marks the draft state.

Lax5.NowhereDenseNC

Nowhere dense classes have almost linear neighborhood complexity

concepts/Lax5/NowhereDenseNC.lean · Lax5

proven

Theorem

Every nowhere dense graph class has almost linear neighborhood complexity: for every ε > 0 there is a constant c such that every member G and every nonempty vertex subset A satisfy |{N(v) ∩ A : v ∈ V(G)}| ≤ c · |A|^(1+ε).

Lean source view on GitHub

1import Lax5.NeighborhoodComplexity
2import Lax5.NowhereDenseClasses
3
4/-!
5---
6title: Nowhere dense classes have almost linear neighborhood complexity
7type: theorem
8---
9Every nowhere dense graph class has almost linear neighborhood
10complexity: for every ε > 0 there is a constant *c* such that every
11member *G* and every nonempty vertex subset *A* satisfy
12|{N(v) ∩ A : v ∈ V(G)}| ≤ *c* · |A|^(1+ε).
13
14# Formalization notes
15
16The conclusion is the shared predicate `HasAlmostLinearNC` of the
17neighborhood complexity concept; the hypothesis is the shallow-minor
18definition of the nowhere dense concept. This is the radius-1 case of a
19classical result on nowhere dense classes (Eickmeyer, Giannopoulou,
20Kreutzer, Kwon, Pilipczuk, Rabinovich, Siebertz).
21-/
22
23namespace Lax5.NowhereDenseNC
24
25open Lax5.GraphClasses Lax5.NeighborhoodComplexity Lax5.NowhereDenseClasses
26
27/-- Nowhere dense graph classes have almost linear neighborhood
28complexity. -/
29axiom hasAlmostLinearNC_of_nowhereDense
30 (C : GraphClass) (h : NowhereDense C) :
31 HasAlmostLinearNC C
32
33end Lax5.NowhereDenseNC
34

Formalization notes

The conclusion is the shared predicate HasAlmostLinearNC of the neighborhood complexity concept; the hypothesis is the shallow-minor definition of the nowhere dense concept. This is the radius-1 case of a classical result on nowhere dense classes (Eickmeyer, Giannopoulou, Kreutzer, Kwon, Pilipczuk, Rabinovich, Siebertz).

Imported

Imported by

none

Mathlib imports

none