Lax5Almost Linear Neighborhood Complexity of Monadically Dependent Graph Classes
Abstract
This submission states Theorem 2 of Dreier, Mählmann, McCarty, Pilipczuk, Toruńczyk, Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes (2026): every monadically dependent class of finite graphs has almost linear neighborhood complexity — for every $\varepsilon > 0cG$ and every nonempty vertex subset satisfy .
The concept surface has eleven review units. Six definitions: graph classes on the canonical vertex types; non-copying first-order transductions between classes of arbitrary relational structures (a domain formula and one formula per target relation symbol, over a monadic color expansion); graph transductions as the special case over the language of graphs; monadic dependence (the class does not transduce all graphs); neighborhood complexity, with the shared bound predicate ; and nowhere denseness via shallow-minor models. Five theorems: weakly sparse monadically dependent classes are nowhere dense; nowhere dense classes have subpolynomial weak coloring numbers, uniformly over subgraphs of members; nowhere dense classes have almost linear neighborhood complexity; the headline theorem; and nowhere dense classes are monadically dependent (Adler–Adler).
The proof package discharges the headline theorem via the paper's VC-dimension sparsification argument; the nowhere dense counting statement from the coloring-number theorem, via radius-1 trace counting along a weak coloring order and localization; the weakly sparse theorem via Mählmann's Ramsey-theoretic extraction of induced subdivided bicliques (thesis, Lemma 13.8) together with a star-crossing transduction of all graphs; and the Adler–Adler direction via uniform quasi-wideness and a semantic locality argument — the deletion specialization of the flip-breakability route, with hereditarily finite rank-bounded local types of decorated balls and a ball-swap back-and-forth system in place of Gaifman's theorem. A transduction of all graphs would shatter arbitrarily large sets; quasi-wide scattering, a local-type pigeonhole, and the swap lemma refute this. With that, all five theorem concepts are proved, and every one reports only Lean's standard logical axioms — the surface carries the full classical equivalence that on weakly sparse classes, monadic dependence and nowhere denseness coincide.
Concepts
- thm✓
Lax5.AdlerAdler - thm✓
Lax5.AlmostLinearNC - def
Lax5.GraphClasses - def
Lax5.GraphTransductions - def
Lax5.MonadicDependence - def
Lax5.NeighborhoodComplexity - def
Lax5.NowhereDenseClasses - thm✓
Lax5.NowhereDenseNC - thm✓
Lax5.NowhereDenseWcol - def
Lax5.Transductions - thm✓
Lax5.WeaklySparseDependent
Proofs
-
assuming nothing
-
assuming nothing
-
assuming nothing
-
assuming nothing
-
assuming nothing
Proof code is not displayed; the archive records each proof's checked relationship between statements.
Cite this
@misc{Lax5,
author = {Jan Dreier},
title = {Almost Linear Neighborhood Complexity of Monadically Dependent Graph Classes},
year = {2026},
howpublished = {Lax Archive, Lax5},
url = {https://laxarchive.org/Lax5/},
note = {draft},
}
References
@misc{DreierMahlmannMcCartyPilipczukTorunczyk2026,
author = {Dreier, Jan and M{\"a}hlmann, Nikolas and McCarty, Rose
and Pilipczuk, Micha{\l} and Toru{\'n}czyk, Szymon},
title = {Neighborhood Complexity and Radius-1 Merge-Width in
Monadically Dependent Graph Classes},
year = {2026},
eprint = {2607.10941},
archivePrefix = {arXiv}
}
@phdthesis{Mahlmann2024,
author = {M{\"a}hlmann, Nikolas},
title = {Monadically Stable and Monadically Dependent Graph Classes:
Characterizations and Algorithmic Meta-Theorems},
school = {Universit{\"a}t Bremen},
year = {2024}
}
@inproceedings{DreierMahlmannTorunczyk2024,
author = {Dreier, Jan and M{\"a}hlmann, Nikolas and Toru{\'n}czyk,
Szymon},
title = {Flip-Breakability: A Combinatorial Dichotomy for
Monadically Dependent Graph Classes},
booktitle = {Proceedings of the 56th Annual ACM Symposium on Theory
of Computing (STOC 2024)},
year = {2024},
eprint = {2403.15201},
archivePrefix = {arXiv}
}
@article{AdlerAdler2014,
author = {Adler, Hans and Adler, Isolde},
title = {Interpreting nowhere dense graph classes as a classical
notion of model theory},
journal = {European Journal of Combinatorics},
volume = {36},
pages = {322--330},
year = {2014},
doi = {10.1016/j.ejc.2013.06.048}
}