arXiv preprint ·
Small classes have linear neighbourhood complexity
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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 every small class. In particular, every small class admits an adjacency labelling scheme with $O(\log^2 n)$-bit labels, improving the previous $O(\log^3 n)$ bound.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Combinatorics
Explicit Subspace Evasive Sets via Subspace Designs
Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs
Improved Lower Bounds for Mutually Orthogonal Latin Squares (MOLS) at 33 Orders
Integrality Gap of 3.4 for Santa Claus: A Topology-based Analysis
When Elements Fail: Weighted Fault-Tolerant Matroid Bases
Get the few papers worth your time in Combinatorics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.