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

Lax5Almost Linear Neighborhood Complexity of Monadically Dependent Graph Classes

Jan Dreier

created 2026-07-24·github.com/jan3er/lax-submissions@e329e64/monadic-dependence-neighborhood-complexity·Lean v4.30.0 · mathlib c5ea00351c28

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 > 0thereisa there is a csuchthateverymember such that every member G$ and every nonempty vertex subset AA satisfy {N(v)A:vV(G)}cA1+ε|\{N(v) \cap A : v \in V(G)\}| \le c\,|A|^{1+\varepsilon}.

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 A1+o(1)|A|^{1+o(1)}; 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

Dependency view
This submissionOther submissionDependency to importer

Proofs

Derivation viewArrows follow logical support
Proven statementUnproven statementExternal nodeProofCycleUngrounded cycle

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}
}