论文标题
顶点有序图中的瓷砖图
Tilings in vertex ordered graphs
论文作者
论文摘要
近年来，对顶点有序图的Turán和Ramsey属性都引起了极大的兴趣。在本文中，我们将嵌入结构嵌入到顶点有序图中的研究。特别是，我们引入了一个通用框架，以解决确定在有序图中强迫完美$ h $的最低度阈值的问题。在（无序的）图设置中，Kühn和Osthus解决了此问题[完美的图形包装的最低度阈值，Combinatorica，2009年]。我们使用一般框架来解决所有有序图的完美$ h $ fisting问题，$ h $的间隔色数$ 2 $。在这种限制的设置中，极端示例的类别比在无序的图形问题中更丰富。在证明我们的结果的过程中，开发了规律性和吸收方法的新方法。
Over recent years there has been much interest in both Turán and Ramsey properties of vertex 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 a perfect $H$-tiling in 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 perfect $H$-tiling problem for all ordered graphs $H$ of 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.
