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, and the nowhere dense counting statement from the coloring-number theorem, via radius-1 trace counting along a weak coloring order and localization. The two remaining obligations — weakly sparse dependent classes are nowhere dense, and the Adler–Adler direction — are deliberately left open as well-defined targets for follow-up submissions; together they carry the 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
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},
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}
}
@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}
}