paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Stable graphs of bounded twin-width

有界 twin-width 的稳定图
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 0/10 · 该论文属于纯图论与模型论研究，讨论图的 twin-width、单调稳定性和 transductions，不涉及程序分析、LLM/Agent、浮点程序分析或贝叶斯程序分析。与用户研究方向几乎没有交集。引用 38 inbox
Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk
逻辑与自动机
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话：证明单调稳定且有界 twin-width 的图类可由有界稀疏 twin-width 的图类经 transductions 得到，并推出线性 χ-有界性。

论文研究图类的模型论稳定性与结构宽度之间的联系，聚焦单调稳定（monadically stable）且 twin-width 有界的图类。作者证明，这类图类可以从某个具有有界稀疏 twin-width 的图类通过 transductions 得到。该结论推广了此前对有界线团宽（linear cliquewidth）图类和有界团宽图类得到的类似结果。作为推论，单调稳定且有界 twin-width 的图类是线性 χ-有界的。这一结果将稳定性条件与稀疏/稠密图类之间的可转导关系联系起来，为相关图类的结构刻画与着色界提供了统一框架。

问题
刻画单调稳定且 twin-width 有界的图类，理解其与有界稀疏 twin-width 图类的关系，并确定其 χ-有界性。
方法
通过 transductions 证明这类图类可由有界稀疏 twin-width 的图类生成，并推广已有线团宽与团宽图类的相应结果。
评估
以理论证明和推论作为评估：主要定理的推导、对已知结果的推广以及线性 χ-有界性推论。
原文摘要（Abstract）

We prove that every class of graphs that is monadically stable and has bounded twin-width can be transduced from some class with bounded sparse twin-width. This generalizes analogous results for classes of bounded linear cliquewidth [Nešetřil et al. 2021b] and of bounded cliquewidth [Nešetřil et al. 2021a]. It also implies that monadically stable classes of bounded twin-width are linearly χ-bounded.

链接与引用

DOI 原文 · arXiv · PDF（开放获取） · DBLP

BibTeX 
@inproceedings{GajarskyPT22,
  title = {Stable graphs of bounded twin-width},
  author = {Jakub Gajarský and Michał Pilipczuk and Szymon Toruńczyk},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533356}
}