Twin-width and types

arXiv2206.08248MaRDI QIDQ6402302FDOQ6402302

Authors: Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, Szymon Toruńczyk 

Publication date: 16 June 2022

Abstract: We study problems connected to first-order logic in graphs of bounded twin-width. Inspired by the approach of Bonnet et al. [FOCS 2020], we introduce a robust methodology of local types and describe their behavior in contraction sequences -- the decomposition notion underlying twin-width. We showcase the applicability of the methodology by proving the following two algorithmic results. In both statements, we fix a first-order formula $varphi(x_1,ldots,x_k)$ and a constant $d$, and we assume that on input we are given a graph $G$ together with a contraction sequence of width at most $d$. (A) One can in time $O(n)$ construct a data structure that can answer the following queries in time $O(loglogn)$: given $w_1,ldots,w_k$, decide whether $phi(w_1,ldots,w_k)$ holds in $G$. (B) After $O(n)$-time preprocessing, one can enumerate all tuples $w_1,ldots,w_k$ that satisfy $phi(x_1,ldots,x_k)$ in $G$ with $O(1)$ delay. In the case of (A), the query time can be reduced to $O(1/varepsilon)$ at the expense of increasing the construction time to $O(n^{1+varepsilon})$, for any fixed $varepsilon>0$. Finally, we also apply our tools to prove the following statement, which shows optimal bounds on the VC density of set systems that are first-order definable in graphs of bounded twin-width. (C) Let $G$ be a graph of twin-width $d$, $A$ be a subset of vertices of $G$, and $varphi(x_1,ldots,x_k,y_1,ldots,y_l)$ be a first-order formula. Then the number of different subsets of $A^k$ definable by $phi$ using $l$-tuples of vertices from $G$ as parameters, is bounded by $O(|A{|}^l)$.

This page was built for publication: Twin-width and types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402302)