Tilings in vertex ordered graphs
Tilings in vertex ordered graphs
复制标题
顶点有序图中的平铺
DOI：
10.1016/j.jctb.2022.02.006
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Treglown, Andrew
中科院分区：
文献类型：
--
作者：
Balogh, József;Li, Lina;Treglown, Andrew
近年来，点序图的Turán性质和Ramsey性质引起了人们的极大兴趣.在这篇论文中，我们开始研究在点序图中嵌入生成结构。特别是，我们介绍了一个一般的框架，接近的问题，确定最低程度的阈值，迫使一个完美的H-tilingin有序图。在（无序）图设置中，这个问题由Kühn和Osthus解决[完美图填充的最小度阈值，Combinatorica，2009]。我们使用我们的一般框架来解决区间色数为2的所有有序图H的完美H-平铺问题。已经在这个限制设置类极值的例子是丰富的比无序图的问题。在证明我们的结果的过程中，新的方法的规律性和吸收方法的发展。
Over recent years there has been much interest in both Turán and Ramsey properties ofvertex ordered graphs. In this paper we initiate the study of embedding spanning structures into vertex ordered graphs. In particular, we introduce a general framework for approaching the problem of determining the minimum degree threshold for forcing aperfect H-tilingin an ordered graph. In the (unordered) graph setting, this problem was resolved by Kühn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009]. We use our general framework to resolve the perfectH-tiling problem for all ordered graphsHof interval chromatic number 2. Already in this restricted setting the class of extremal examples is richer than in the unordered graph problem. In the process of proving our results, novel approaches to both the regularity and absorbing methods are developed.