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@aa7e3ed/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:v∈V(G)}∣≤c ∣A∣1+ε|\{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 ∣A∣1+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, 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

Dependency view
This submissionOther submission→Dependency to importer

Proofs

Derivation viewArrows follow logical support
Proven statementUnproven statementExternal node⊢ProofCycleUngrounded 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},
  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}
}