论文标题
有限双宽度图的远端组合工具
Distal combinatorial tools for graphs of bounded twin-width
论文作者
论文摘要
我们研究由界图双宽度图中的社区形成的集合系统。首先，我们证明了此类图具有线性邻域复杂性，类似于先前的结果，该结果来自具有有限膨胀和有界组宽度的类的图形。接下来，我们将注意力转移到远距离和抽象细胞分解的概念上，这些概念来自模型理论。我们给出了一个直接的组合证据，表明边缘关系在有界双宽的有序图中是远端。这使我们可以应用远端切割引理和远端规则性引理，因此我们获得了有界双宽度图的强大组合工具。
We study set systems formed by neighborhoods in graphs of bounded twin-width. We start by proving that such graphs have linear neighborhood complexity, in analogy to previous results concerning graphs from classes with bounded expansion and of bounded clique-width. Next, we shift our attention to the notions of distality and abstract cell decomposition, which come from model theory. We give a direct combinatorial proof that the edge relation is distal in classes of ordered graphs of bounded twin-width. This allows us to apply Distal cutting lemma and Distal regularity lemma, so we obtain powerful combinatorial tools for graphs of bounded twin-width.
