Neighbourhood complexity of graphs of bounded twin-width

Abstract

<p>We give essentially tight bounds for, <em>ν(d, k)</em>, the maximum number of distinct neighbourhoods on a set <em>X</em> of <em>k</em> vertices in a graph with twin-width at most d. Using the celebrated Marcus–Tardos theorem, two independent works (Bonnet et al., 2022; Przybyszewski, 2022) have shown the upper bound <em>ν(d, k) ⩽ exp(exp(O(d)))k</em>, with a double-exponential dependence in the twin-width. The work of Gajarsky et al. (2022), using the framework of local types, implies the existence of a single-exponential bound (without explicitly stating such a bound). We give such an explicit bound, and prove that it is essentially tight. Indeed, we give a short self-contained proof that for every <em>d</em> and <em>k</em></p><p><em>ν(d, k) ⩽ (d + 2)2^d+1k = 2^{d+log d+Θ(1)}k</em>,</p><p>and build a bipartite graph implying <em>ν(d, k) ⩾ 2^{d+log d+Θ(1)}k</em>, in the regime when k is large enough compared to <em>d</em>.<br></p>