Neighbourhood complexity of graphs of bounded twin-width
share
We give essentially tight bounds for, ν(d,k), the maximum number of distinct neighbourhoods on a set X of k vertices in a graph with twin-width at most d. Using the celebrated Marcus-Tardos theorem, two independent works [Bonnet et al., Algorithmica '22; Przybyszewski '22] have shown the upper bound ν(d,k) ⩽exp(exp(O(d)))k, with a double-exponential dependence in the twin-width. We give a short self-contained proof that for every d and k, ν(d,k) ⩽ (d+2)2^d+1k = 2^d+O(log d)k, and build a bipartite graph implying ν(d,k) ⩾ 2^d+log d+O(1)k, in the regime when k is large enough compared to d.
READ FULL TEXT