paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Distal Combinatorial Tools for Graphs of Bounded Twin-Width

有界 twin-width 图的 distal 组合工具
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 0/10 · 该论文研究有界 twin-width 图的组合学与模型论工具(distal 切割/正则引理),属于纯图论与逻辑/自动机理论,与用户关注的 PL-AI、静态分析、Agentic 程序、浮点程序分析、贝叶斯程序分析及 LLM 交叉方向均无直接关联。引用 7 inbox
Wojciech Przybyszewski
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:证明有界 twin-width 图具线性邻域复杂度,并借助边关系 distal 获得 distal 切割与正则引理。

本文研究有界 twin-width 图中由邻域构成的集合系统,目标是为此类图建立类似有界扩张和有界 clique-width 的组合工具。作者首先证明这类图具有线性邻域复杂度。随后引入模型论中的 distality 与抽象胞腔分解(abstract cell decomposition),并给出组合证明:在有序且 twin-width 有界的图上,边关系是 distal 的。由此可应用 distal cutting lemma 与 distal regularity lemma,得到一套可用于有界 twin-width 图的强组合工具。评估为纯理论证明,未报告实验。

问题
研究有界 twin-width 图的邻域集合系统,并寻求可迁移的模型论与组合学工具,如线性邻域复杂度、distality 与正则性引理。
方法
证明线性邻域复杂度;对有序有界 twin-width 图给出边关系 distality 的直接组合证明,并应用 distal cutting/regularity lemma。
评估
通过数学证明与引理推导进行评估,未涉及实现或实验。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@inproceedings{Przybyszewski23,
  title = {Distal Combinatorial Tools for Graphs of Bounded Twin-Width},
  author = {Wojciech Przybyszewski},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175719}
}