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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-11 Page: https://delphi.science/r/arxiv/2611.15299 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…