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