Twin-width IV: ordered graphs and matrices
Twin-width IV: ordered graphs and matrices
复制标题
DOI：
10.1145/3519935.3520037
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
'Edouard Bonnet;Ugo Giocanti;P. D. Mendez;Pierre Simon;St'ephan Thomass'e;Szymon Toruńczyk
中科院分区：
文献类型：
--
作者：
'Edouard Bonnet;Ugo Giocanti;P. D. Mendez;Pierre Simon;St'ephan Thomass'e;Szymon Toruńczyk
我们建立了全序图的遗传类的有界孪生宽度的一系列特征：作为在计数组合学中研究的最多指数增长的类，作为在模型论中研究的Monadically NIP类，作为在有限模型论中研究的不包含所有图的类的类，以及作为在算法图论中研究的模型检查一阶逻辑是固定参数易处理的类。这有几个后果。首先，它允许我们证明，每一个遗传类的有序图要么有最多指数增长，或至少有阶乘增长。这解决了一个问题首先问Balogh，Bollobás和莫里斯[欧洲。J. Comb.'06]关于有序图的遗传类的增长，推广了Stanley-Wilf猜想/Marcus-Tardos定理。其次，给出了一个求有序图的孪生宽度的固定参数近似算法。第三，它产生了一个完整的分类固定参数听话的一阶模型检查的有序二元结构的遗传类。第四，它提供了一个有界孪生宽度类的模型论特征。最后，它解决了我们的小猜想[SODA '21]在有序图的情况下。
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobás, and Morris [Eur. J. Comb. ’06] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles our small conjecture [SODA ’21] in the case of ordered graphs.