Pith. sign in

REVIEW 4 minor 41 references

Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes

T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Monadically dependent graph classes have almost-linear neighborhood complexity and almost-bounded radius-1 merge-width.

desk verdict Solid, fully proved advance: monadic dependence implies almost-linear neighborhood complexity and almost-bounded radius-1 merge-width, with an explicit O(n^5) algorithm. read the letter →

arxiv 2607.10941 v1 pith:6TQBWDKI submitted 2026-07-12 cs.DM cs.DScs.LOmath.CO

Jan Dreier , Nikolas Mählmann , Rose McCarty , Micha{l} Pilipczuk , Szymon Toruńczyk This is my paper · ORCID
classification cs.DMcs.DScs.LOmath.CO MSC 05C7568Q2503C13
keywords monadicdependenceneighborhoodcomplexitymerge-widthconstructionsequencesVC-dimensionfirst-ordermodelcheckinghereditarygraphclasses
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Monadic dependence is a candidate dividing line that is hoped to characterize exactly when first-order model checking is fixed-parameter tractable on hereditary graph classes. This paper proves two concrete structural consequences of that property. First, every graph from a monadically dependent class has almost-linear neighborhood complexity: for any vertex set A the number of distinct neighborhoods restricted to A is at most |A| to the power 1+o(1). Second, every n-vertex graph in such a class admits a construction sequence whose radius-1 merge-width is only n to the o(1). The second statement is obtained algorithmically: whenever neighborhoods are polynomial of degree d, an O(n^5) procedure builds a construction sequence of radius-1 width O(n^{1-1/d} log n). Together the results give the first decomposition-based description of monadically dependent classes and settle the radius-1 case of a recent conjecture linking monadic dependence to almost-bounded merge-width.

What carries the argument

Inductive sparsification of bipartite graphs that repeatedly extracts a large subset whose neighborhoods have strictly smaller VC-dimension, combined with a greedy leader-merge algorithm that reweights fractional twins via Haussler’s packing lemma.

What would settle it

Exhibit a hereditary monadically dependent class that contains, for arbitrarily large A, more than |A|^{1+ε} distinct neighborhoods on A for some fixed ε>0, or show that some n-vertex graph of polynomial neighborhood complexity has radius-1 merge-width ω(n^{1-1/d} log n).

Watch

Extended reading notes

Core claim

Every monadically dependent hereditary graph class has almost-linear neighborhood complexity, and therefore every n-vertex graph in the class has radius-1 merge-width n^{o(1)}. Moreover, any graph whose neighborhoods are bounded by a polynomial of degree d admits, in O(n^5) time, an explicit construction sequence of radius-1 merge-width O(n^{1-1/d} log n).

Load-bearing premise

The argument that monadic dependence forces almost-linear neighborhoods rests on the classical fact that a monadic-dependent bipartite class free of a fixed complete bipartite subgraph is already nowhere dense.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper proves that every monadically dependent hereditary graph class has almost-linear neighborhood complexity (Theorem 2): for G in the class and Asubseteq V(G), the number of distinct neighborhoods N(v) cap A is |A|^{1+o(1)}. From this it derives that every n-vertex graph in such a class has radius-1 merge-width n^{o(1)} (Theorem 4). The argument is algorithmic: Theorem 5 supplies an O(n^5)-time procedure that, given any n-vertex graph whose neighborhood complexity is O(|A|^d), returns a construction sequence of radius-1 width O(n^{1-1/d} log n). The neighborhood-complexity proof proceeds by induction on VC-dimension via k-sparsifications (Definition 22), Hamming/merge graphs, Haussler packing, and a reduction to the nowhere-dense base case (Corollary 6). The merge-width algorithm uses multiplicative weight updates and fractional twins (Lemmas 13-14).

Significance. The results give the first decomposition-based structural description of monadically dependent classes and settle the radius-1 case of the Dreier-Toruńczyk conjecture linking monadic dependence to almost-bounded merge-width. Almost-linear neighborhood complexity immediately yields Welzl orderings, sparse neighborhood covers, spanners, adjacency labeling schemes, and n^{2+o(1)} APSP (Corollary 3), extending these tools beyond the previously settled regimes of nowhere denseness and monadic stability. The O(n^5) algorithm of Theorem 5 is fully explicit, self-contained, and works for any graph of polynomial neighborhood complexity; the classical packing and reweighting ingredients are used cleanly. Together the theorems supply a concrete algorithmic foothold toward FO model checking on monadically dependent classes.

minor comments (4)
  1. [Theorem 5 / end of Section 3] The O(n^5) bound of Theorem 5 is left unoptimized; a short remark comparing it with the near-linear signed-tree constructions known for twin-width would help the reader gauge practicality.
  2. [Definition 22] Definition 22 of k-sparsification is dense; a one-sentence intuition that the functions f_j encode a FO-definable partition of controlled VC-dimension would improve readability before the inductive lemmas.
  3. [Section 2, after Lemma 12] In the high-level overview (Section 2) the polylog factors lost at each of the d sparsification steps are stated only asymptotically; an explicit product of the constants from Lemmas 11-12 would make the dependence on d transparent.
  4. [Figure 1] Figure 1 is reproduced from [16]; a brief caption sentence explaining which stages illustrate radius-1 width three would make the figure self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: neighborhood-complexity bound and radius-1 construction sequence are derived from monadic dependence via VC-dimension induction, packing lemmas, and classical nowhere-dense facts, without reducing to their own inputs.

full rationale

The derivation chain begins from the model-theoretic definition of monadic dependence (no FO-interpretation of all graphs), extracts bounded VC-dimension of the neighborhood set system, then applies an inductive sparsification (Lemmas 19–26) that repeatedly lowers VC-dimension while losing only polylog factors, terminating in a K_{d+1,d+1}-free FO-transducible bipartite graph to which the classical almost-linear neighborhood-complexity bound for nowhere-dense classes (Corollary 6, via Adler–Adler + Dvořák) applies. The radius-1 merge-width algorithm (Theorem 5) is a self-contained multiplicative-weight greedy procedure that takes only a polynomial neighborhood-complexity hypothesis as input and produces an explicit construction sequence; monadic dependence is used solely to guarantee that hypothesis via Theorem 2. Self-citations ([16] for the definition of merge-width, prior monadic-dependence papers) supply definitions and the open conjecture being partially settled; they are not load-bearing for the proofs themselves, which rely on Haussler packing, Sauer–Shelah, and Welzl-style reweighting. No equation is forced by construction from a fitted parameter, no uniqueness theorem is imported to forbid alternatives, and no ansatz is smuggled. The results are therefore independent of their own conclusions.

Assumptions & free parameters 1 free parameters · 4 assumptions · 1 invented entities

The paper rests on standard combinatorial lemmas (Sauer–Shelah, Haussler packing, Welzl reweighting) and on the model-theoretic definition of monadic dependence together with its known consequences for nowhere-dense classes. No free parameters are fitted to data; the only constants are those supplied by the packing lemma. The sole invented intermediate object is the k-sparsification used in the inductive argument.

free parameters (1)
  • r(c,d) / k(c,d) from Haussler packing
    Integer constants whose existence is guaranteed by Haussler’s Packing Lemma; they appear in the fractional-twin guarantee and the final width bound but are never numerically fitted.
assumptions (4)
  • domain assumption Monadic dependence implies bounded VC-dimension of the neighborhood set system
    Standard and elementary; used at the start of the NC proof.
  • domain assumption A monadically dependent class free of K_{t,t} is nowhere dense and therefore has almost-linear neighborhood complexity (Corollary 6)
    Cited from Adler–Adler and Dvořák; load-bearing for the base of the induction.
  • standard math Haussler’s Packing Lemma (Lemma 27)
    Classical; supplies the fractional-twin constant r(c,d).
  • standard math Sauer–Shelah–Perles lemma and the Hamming-graph edge bound of Haussler–Littlestone–Warmuth
    Used to control VC-dimension drop and non-isolated vertices.
invented entities (1)
  • k-sparsification (Definition 22)
    purpose: Inductive intermediate that packages a large subset of B together with k definable functions that reduce VC-dimension while preserving injectivity of neighborhoods.
    Purely technical device internal to the proof of almost-linear NC; no independent existence claim.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes." pith.science (2026). https://pith.science/paper/6TQBWDKI

@misc{pith2026260710941,
  author       = {Pith},
  title        = {Pith review of: Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6TQBWDKI}},
  note         = {Machine review of arXiv:2607.10941}
}
abstract

Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadically dependent} if the class of all graphs cannot be interpreted in its vertex-colored members using a fixed first-order formula. We prove two structural consequences of monadic dependence. First, every monadically dependent class has \emph{almost linear neighborhood complexity}: for every graph $G$ in the class and every set $A\subseteq V(G)$, the family $\{N_G(v)\cap A : v\in V(G)\}$ has size $|A|^{1+o(1)}$. Second, every $n$-vertex graph in a monadically dependent class has radius-1 merge-width $n^{o(1)}$. Here, merge-width is the decomposition parameter of Dreier and Toru\'nczyk based on construction sequences; its radius-$r$ version measures local reachability among parts through already resolved pairs. This settles the radius-1 case of the conjectured connection between monadic dependence and almost bounded merge-width and provides the first decomposition-based structural description of monadically dependent graph classes. Our proof is algorithmic: we give an $\mathcal{O}(n^5)$-time algorithm that, given an $n$-vertex graph $G$ such that $|\{N_G(v)\cap A : v\in V(G)\}|\le O(|A|^d)$ for every $A\subseteq V(G)$, computes a construction sequence witnessing radius-1 merge-width $\mathcal{O}(n^{1-1/d}\log n)$.

Figures

Figures reproduced from arXiv: 2607.10941 by the authors.

Figure 1
Figure 1. A construction sequence of a graph witnessing radius-1 merge-width at most three. The [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 3 linked inside Pith

  1. [1]

    https://warwick.ac.uk/fac/sci/maths/people/staff/daniel_kral/alglogstr/ openproblems.pdf, 2016

    Algorithms, Logic and Structure Workshop in Warwick – Open Problem Ses- sion. https://warwick.ac.uk/fac/sci/maths/people/staff/daniel_kral/alglogstr/ openproblems.pdf, 2016. [Online; accessed 23-Jan-2023]

    2016

  2. [2]

    Interpreting nowhere dense graph classes as a classical notion of model theory.European Journal of Combinatorics, 36:322–330, 2014

    Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory.European Journal of Combinatorics, 36:322–330, 2014. 11

    2014

  3. [3]

    Implicit representation of sparse hereditary families.Discrete & Computational Geometry, 72(2):476–482, July 2023

    Noga Alon. Implicit representation of sparse hereditary families.Discrete & Computational Geometry, 72(2):476–482, July 2023

    2023

  4. [4]

    Second-order quantifiers and the complexity of theories

    John T Baldwin and Saharon Shelah. Second-order quantifiers and the complexity of theories. Notre Dame Journal of Formal Logic, 26(3):229–303, 1985

    1985

  5. [5]

    Marthe Bonamy and Colin Geniet.χ-boundedness and neighbourhood complexity of bounded merge-width graphs.Arxiv preprint 2504.08266, 2025

    arXiv 2025

  6. [6]

    Adjacency labeling schemes for small classes

    Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev. Adjacency labeling schemes for small classes. In16th Innovations in Theoretical Computer Science Conference, ITCS 2025, LIPIcs, pages 21:1–21:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025

    2025

  7. [7]

    Twin-width III: Max Independent Set, Min Dominating Set, and Coloring

    Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. In48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, volume 198 ofLIPIcs, pages 35:1–35:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021

    2021

  8. [8]

    Twin-width IV: Ordered graphs and matrices

    Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Toruńczyk. Twin-width IV: Ordered graphs and matrices. In54th Annual ACM Symposium on Theory of Computing, STOC 2022, pages 924–937, 2022

    2022

Show all 41 references
  1. [9]

    Twin-width I: tractable FO model checking.Journal of the ACM, 69(1):1–46, 2021

    Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking.Journal of the ACM, 69(1):1–46, 2021

    2021

  2. [10]

    Quasi-optimal range searching in spaces of finite VC-dimension

    Bernard Chazelle and Emo Welzl. Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom., 4(5):467–489, 1989

    1989

  3. [11]

    Linear time solvable optimization problems on graphs of bounded clique-width.Theory of Computing Systems, 33(2):125–150, 2000

    Bruno Courcelle, Johann A Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory of Computing Systems, 33(2):125–150, 2000

    2000

  4. [12]

    First-order model checking on monadically stable graph classes

    Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michał Pilipczuk, and Szymon Toruńczyk. First-order model checking on monadically stable graph classes. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, pages 21–30. IEEE, 2024

    2024

  5. [13]

    Near-linear time computation of Welzl orders on graphs with linear neighborhood complexity.Arxiv preprint 2602.14625, 2026

    Jan Dreier and Clemens Kuske. Near-linear time computation of Welzl orders on graphs with linear neighborhood complexity.Arxiv preprint 2602.14625, 2026

    2026

  6. [14]

    First-order model checking on struc- turally sparse graph classes

    Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. First-order model checking on struc- turally sparse graph classes. In55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 567–580. ACM, 2023

    2023

  7. [15]

    Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes

    Jan Dreier, Nikolas Mählmann, and Szymon Toruńczyk. Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes. In56th Annual ACM Symposium on Theory of Computing, STOC 2024, pages 1550–1560. ACM, 2024

    2024

  8. [16]

    Merge-width and first-order model checking

    Jan Dreier and Szymon Toruńczyk. Merge-width and first-order model checking. In57th Annual ACM Symposium on Theory of Computing, STOC 2025, pages 1944–1955. ACM, 2025. 12

    2025

  9. [17]

    Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs

    Lech Duraj, Filip Konieczny, and Krzysztof Potępa. Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs. In32nd Annual European Symposium on Algorithms, ESA 2024, LIPIcs, pages 51:1–51:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024

    2024

  10. [18]

    Induced subdivisions and bounded expansion.European Journal of Combina- torics, 69:143–148, 2018

    Zdeněk Dvořák. Induced subdivisions and bounded expansion.European Journal of Combina- torics, 69:143–148, 2018

    2018

  11. [19]

    Testing first-order properties for subclasses of sparse graphs.J

    Zdeněk Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs.J. ACM, 60(5):36:1–36:24, 2013

    2013

  12. [20]

    Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz

    Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood complexity and ker- nelization for nowhere dense classes of graphs. In44th International Colloquium on Automata, Languages, and P...

    2017

  13. [21]

    Jakub Gajarský, Petr Hliněný, Jan Obdržálek, Daniel Lokshtanov, and M. S. Ramanujan. A new perspective on FO model checking of dense graph classes. In31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016, pages 176–184. ACM, 2016

    2016

  14. [22]

    Deciding first-order properties of nowhere dense graphs.Journal of the ACM, 64(3):1–32, 2017

    Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs.Journal of the ACM, 64(3):1–32, 2017

    2017

  15. [23]

    Haussler, N

    D. Haussler, N. Littlestone, and M.K. Warmuth. Predicting 0, 1-functions on randomly drawn points.Information and Computation, 115(2):248–292, 1994

    1994

  16. [24]

    Sphere packing numbers for subsets of the Booleann-cube with bounded Vapnik-Chervonenkis dimension.Journal of Combinatorial Theory, Series A, 69(2):217–232, 1995

    David Haussler. Sphere packing numbers for subsets of the Booleann-cube with bounded Vapnik-Chervonenkis dimension.Journal of Combinatorial Theory, Series A, 69(2):217–232, 1995

    1995

  17. [25]

    PhD thesis, University of Bremen, 2024

    Nikolas Mählmann.Monadically Stable and Monadically Dependent Graph Classes: Characteri- zations and Algorithmic Meta-Theorems. PhD thesis, University of Bremen, 2024

    2024

  18. [26]

    Springer Berlin Heidelberg, 1999

    Jiří Matoušek.Geometric Discrepancy. Springer Berlin Heidelberg, 1999

    1999

  19. [27]

    Rankwidth meets stability

    Jaroslav Nešetřil, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Rankwidth meets stability. In2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pages 2014–2033. SIAM, 2021

    2021

  20. [28]

    Graph spanners.Journal of Graph Theory, 13(1):99–116, 1989

    David Peleg and Alejandro A Schäffer. Graph spanners.Journal of Graph Theory, 13(1):99–116, 1989

    1989

  21. [29]

    Chapter 1: Measuring sparsity

    Michał Pilipczuk and Sebastian Siebertz. Chapter 1: Measuring sparsity. Lecture notes for the courseSparsity, winter term 2017/18, University of Warsaw, 2017

    2017

  22. [30]

    Flipping and forking.ArXiv preprint 2505.16745, 2025

    Wojciech Przybyszewski and Szymon Toruńczyk. Flipping and forking.ArXiv preprint 2505.16745, 2025

    2025 arXiv

  23. [31]

    On the density of families of sets.Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972

    Norbert Sauer. On the density of families of sets.Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972

    1972

  24. [32]

    A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific Journal of Mathematics, 41(1):247–261, 1972

    Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages.Pacific Journal of Mathematics, 41(1):247–261, 1972. 13

    1972

  25. [33]

    Flip-width: Cops and robber on dense graphs

    Szymon Toruńczyk. Flip-width: Cops and robber on dense graphs. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 663–700. IEEE Computer Society, 2023. Full version available athttps://arxiv.org/abs/2302.00352

    2023 arXiv

  26. [34]

    E. Welzl. Partition trees for triangle counting and other range searching problems. InFourth Annual Symposium on Computational Geometry, SoCG 1988, page 23–33. ACM, 1988

    1988

  27. [35]

    Fast shortest path in graphs with sparse signed tree models and applications.Arxiv preprint 2602.16605, 2026

    Édouard Bonnet, Colin Geniet, Eun Jung Kim, and Sungmin Moon. Fast shortest path in graphs with sparse signed tree models and applications.Arxiv preprint 2602.16605, 2026. A Neighborhood Complexity In this appendix, we give the full proof of Theorem 2. We begin by introducing ...

    2026

  28. [36]

    a nonterminal k-sparsification can be improved to a(k + 1)-sparsification with strictly smaller dimension, by losing only apolylog(|A|)factor in the size, and increasing the complexity only by a constant (Lemma 25)

  29. [37]

    repeating this argument, we reach a terminal sparsification after at mostd steps, where d upper bounds the VC-dimension of everyGinB(Lemma 26); 16

  30. [38]

    Combining these three points yields a terminalk-sparsification withk⩽dand sizessatisfying |B| polylogd(|A|) ⩽s⩽|A| ·subpoly B,d(|A|)

    a terminal k-sparsification of G∈B of bounded complexity has sizes⩽|A| ·subpoly B,k(|A|) (Lemma 24). Combining these three points yields a terminalk-sparsification withk⩽dand sizessatisfying |B| polylogd(|A|) ⩽s⩽|A| ·subpoly B,d(|A|). This proves the inequality (4) in Lemma 21...

  31. [39]

    Thus, the new sparsification has dimension at most d−1

    The set systemP ′/A1 is a subfamily of the neighborhood ofv in the σ-merge graph of P/A1, so Lemma 10 yields VCdim(P ′/A1)⩽VCdim(P/A 1)−1⩽VCdim(P/A 0)−1⩽d−1, where the second inequality holds asA1 ⊆A 0. Thus, the new sparsification has dimension at most d−1. Second, the size o...

  32. [40]

    for all distinct verticesu, v∈Y , there are at leastδ vertices in X which are adjacent to exactly one ofuandv, and

  33. [41]

    Now we can use Lemma 27 to prove the key lemma about fractional twins

    for every nonemptyA⊆X, we have|{N(v)∩A:v∈Y}|⩽c|A| d, then|Y|⩽max t·(|X|/δ) d,1 . Now we can use Lemma 27 to prove the key lemma about fractional twins. 21 Lemma 13( ♣).For all real numbers c and d⩾ 1, there exists an integerr = r(c, d)so that if G is ann-vertex graph such that...

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.