A1 Refereed original research article in a scientific journal

Neighbourhood complexity of graphs of bounded twin-width




AuthorsBonnet Éouard, Foucaud Florent, Lehtilä Tuomo, Parreau Aline

PublisherAcademic Press

Publication year2023

JournalEuropean Journal of Combinatorics

Journal name in sourceEuropean Journal of Combinatorics

Article number103772

Volume115

ISSN0195-6698

eISSN1095-9971

DOIhttps://doi.org/10.1016/j.ejc.2023.103772

Web address https://doi.org/10.1016/j.ejc.2023.103772

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/180959727


Abstract

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., 2022; Przybyszewski, 2022) have shown the upper bound ν(d, k) ⩽ exp(exp(O(d)))k, 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 d and k

ν(d, k) ⩽ (d + 2)2d+1k = 2d+log d+Θ(1)k,

and build a bipartite graph implying ν(d, k) ⩾ 2d+log d+Θ(1)k, in the regime when k is large enough compared to d.


Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2025-27-03 at 21:59