{"id":"arxiv/2607.10941","url":"https://arxiv.org/abs/2607.10941","tags":["cs.DM","cs.DS","cs.LO","math.CO"],"score":0,"title":"Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes","domain":"cs.DM","source":"arxiv","authors":["Jan Dreier","Nikolas Mählmann","Rose McCarty","Michał Pilipczuk","Szymon Toruńczyk"],"reviews":0,"subject":"cs.DM","summary":"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)}$.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-12","reactions":{}}