Ordered graphs of bounded twin-width
Ordered graphs of bounded twin-width
复制标题
有界双宽有序图
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Szymon Toruńczyk
中科院分区：
文献类型：
--
作者：
Pierre Simon;Szymon Toruńczyk
我们考虑遗传类的图配备了全阶。我们提供了多个等价的特征，这些类有界的孪生宽度。特别地，我们证明了一类有序图，其中有无界的孪生宽度的网格定理。从这一点上，我们得出，一阶逻辑的模型检查问题是固定参数听话的有序图的遗传类，如果和-在常见的复杂性理论假设-只有当类有界双宽度。对于有序图的遗传类，我们证明了有界孪生宽度等价于模型论中的NIP性质，以及计数组合学中的小性条件。我们证明了有序图的遗传类的增长中存在一个缺口。此外，我们提供了一个网格定理，适用于所有单子NIP类的结构（有序或无序），或等价地，类不包括类的所有有限图。
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove a grid theorem for classes of ordered graphs which have unbounded twin-width. From this we derive that the model-checking problem for first-order logic is fixed-parameter tractable over a hereditary class of ordered graphs if, and -- under common complexity-theoretic assumptions -- only if the class has bounded twin-width. For hereditary classes of ordered graphs, we show that bounded twin-width is equivalent to the NIP property from model theory, as well as the smallness condition from enumerative combinatorics. We prove the existence of a gap in the growth of hereditary classes of ordered graphs. Furthermore, we provide a grid theorem which applies to all monadically NIP classes of structures (ordered or unordered), or equivalently, classes which do not transduce the class of all finite graphs.
地图上的 FO 模型检查
DOI：
10.1007/978-3-662-55751-8_17
发表时间：
2017
期刊：
影响因子：
--
作者：
K. Eickmeyer;K. Kawarabayashi
通讯作者：
K. Kawarabayashi