{"ID":6538258,"CreatedAt":"2026-07-14T02:54:43.516908796Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10941","arxiv_id":"2607.10941","title":"Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes","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ńczyk 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)$.","short_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 t...","url_abs":"https://arxiv.org/abs/2607.10941","url_pdf":"https://arxiv.org/pdf/2607.10941v1","authors":"[\"Jan Dreier\",\"Nikolas Mählmann\",\"Rose McCarty\",\"Michał Pilipczuk\",\"Szymon Toruńczyk\"]","published":"2026-07-12T22:04:50Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.DS\",\"cs.LO\",\"math.CO\"]","methods":"[]","has_code":false}