A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Neighbourhood complexity of graphs of bounded twin-width




TekijätBonnet Éouard, Foucaud Florent, Lehtilä Tuomo, Parreau Aline

KustantajaAcademic Press

Julkaisuvuosi2023

JournalEuropean Journal of Combinatorics

Tietokannassa oleva lehden nimiEuropean Journal of Combinatorics

Artikkelin numero103772

Vuosikerta115

ISSN0195-6698

eISSN1095-9971

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

Verkko-osoitehttps://doi.org/10.1016/j.ejc.2023.103772

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/180959727


Tiivistelmä

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.


Ladattava julkaisu

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