论文标题
双宽度和类型
Twin-width and types
论文作者
论文摘要
我们研究与界两个宽度的图表相关的问题。受Bonnet等人的方法的启发。 [焦点2020]，我们介绍了一种局部类型的强大方法，并在收缩序列中描述了它们的行为 - 分解概念是双宽度的基础。我们通过证明以下两个算法结果来展示该方法的适用性。在这两个语句中，我们都修复了一阶公式$φ（x_1，\ ldots，x_k）$和一个常数$ d $，我们假设在输入上，我们将获得图形$ g $，最多在$ d $的宽度上和宽度的收缩顺序。 （a）一个可以在时间$ o（n）$构建数据结构的时间$ o（\ log \ log \ log n）$：给定$ w_1，\ ldots，w_k $，确定$ ϕ（w_1，\ ldots，w_k，w_k）$ in $ g $中。 （b）$ o（n）$ - 时间预处理后，可以列举所有元组$ w_1，\ ldots，w_k $，满足$ ϕ（x_1，\ ldots，x_k）$ g $ in $ g $中的$ o（o（1）$）。 对于（a），对于任何固定的$ \ varepsilon> 0 $，以（n^{1+\ varepsilon}）$将查询时间缩短为$ O（1/\ varepsilon）$，以增加施工时间为$ O（n^{1+\ varepsilon}）$。最后，我们还应用工具来证明以下语句，该语句显示了在界限双宽度图中可以定义的设置系统的VC密度最佳界限。 （c）让$ g $是双宽度$ d $，$ a $的图表，为$ g $的一个子集，$ g $和$φ（x_1，\ ldots，x_k，y_1，y_1，\ ldots，y_l）$是一阶公式。然后，使用$ l $ - $ n $ - $ g $作为参数的顶点定义的$ a^k $的不同子集的数量由$ o（| a |^l）$限制。
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 $φ(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(\log \log n)$: given $w_1,\ldots,w_k$, decide whether $ϕ(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 $ϕ(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 $φ(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 $ϕ$ using $l$-tuples of vertices from $G$ as parameters, is bounded by $O(|A|^l)$.
