{"id":"arxiv/2611.15299","url":"https://arxiv.org/abs/2611.15299","tags":["math.CO","cs.DM"],"score":0,"title":"Small classes have linear neighbourhood complexity","domain":"math.CO","source":"arxiv","authors":["John Sylvester","Viktor Zamaraev","Maksim Zhukovskii"],"reviews":0,"subject":"math.CO","summary":"A hereditary graph class is small if it contains at most $n!c^n$ labelled graphs on $n$ vertices for some constant $c$. Small classes include proper minor-closed classes and classes of bounded twin-width. We prove that every small class has linear neighbourhood complexity, that is, in every graph in the class, vertex neighbourhoods intersect any $k$-vertex set in only $O(k)$ distinct ways. This resolves a conjecture of Bonnet, Duron, and the first two authors (ITCS 2025) and makes the algorithmic, structural, and representation consequences of linear neighbourhood complexity available for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-11","reactions":{}}