一句话:证明有界 twin-width 图具线性邻域复杂度,并借助边关系 distal 获得 distal 切割与正则引理。
本文研究有界 twin-width 图中由邻域构成的集合系统,目标是为此类图建立类似有界扩张和有界 clique-width 的组合工具。作者首先证明这类图具有线性邻域复杂度。随后引入模型论中的 distality 与抽象胞腔分解(abstract cell decomposition),并给出组合证明:在有序且 twin-width 有界的图上,边关系是 distal 的。由此可应用 distal cutting lemma 与 distal regularity lemma,得到一套可用于有界 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.