Delphi.science

Small classes have linear neighbourhood complexity

Source: arxiv.org/abs/2611.15299

John Sylvester, Viktor Zamaraev, Maksim Zhukovskii

arXivarxiv/2611.15299Nov 11, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.15299
curl -X POST /api/v1/records/arxiv/2611.15299/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.15299/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'