Dirac-type results for tilings and coverings in ordered graphs
Dirac-type results for tilings and coverings in ordered graphs
复制标题
有序图中的平铺和覆盖物的狄拉克型结果
DOI：
10.1017/fms.2022.92
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Freschi A
中科院分区：
文献类型：
--
作者：
Freschi A
Balogh，Li和Treglown最近的一篇论文[3]开创了对有序图的Dirac问题的研究。在这篇文章中，我们证明了这方面的一些结果。特别地，我们渐近地确定了如下条件的最小度门限：(I)对于至少具有区间色数的任何固定有序图H，在有序图中进行完美H-平铺；(Ii)对于覆盖G的固定比例的顶点的有序图G(对于任何固定有序图H)；(Iii)在有序图(对于任何固定有序图H)中强制H-覆盖。前两个结果解决了Balogh，Li和Treglown的问题，而(Iii)解决了Falgas-Ravry的问题。请注意，(I)结合[3]的一个结果完全确定了强制完美H-平铺的渐近最小度门限。此外，我们还证明了结合Balogh，Li和Treglown的一个定理，渐近地确定了在一个有序图(对于任何固定有序图H)中强制一个几乎完美H-平铺的最小度门限。因此，我们的工作提供了与Kühn和Ossus[Combinatorica 2009]以及KomlóS[Combinatorica 2000]的种子平铺定理类似的有序图。我们的每个结果都表现出一些奇怪的、或许是意想不到的行为。我们对(I)的解决方案利用了一个新的吸引人的论点。
A recent paper of Balogh, Li and Treglown [3] initiated the study of Dirac-type problems for ordered graphs. In this paper, we prove a number of results in this area. In particular, we determine asymptotically the minimum degree threshold for forcing (i) a perfect H-tiling in an ordered graph, for any fixed ordered graph H of interval chromatic number at least ; (ii) an H-tiling in an ordered graph G covering a fixed proportion of the vertices of G (for any fixed ordered graph H); (iii) an H-cover in an ordered graph (for any fixed ordered graph H). The first two of these results resolve questions of Balogh, Li and Treglown, whilst (iii) resolves a question of Falgas-Ravry. Note that (i) combined with a result from [3] completely determines the asymptotic minimum degree threshold for forcing a perfect H-tiling. Additionally, we prove a result that, combined with a theorem of Balogh, Li and Treglown, asymptotically determines the minimum degree threshold for forcing an almost perfect H-tiling in an ordered graph (for any fixed ordered graph H). Our work therefore provides ordered graph analogues of the seminal tiling theorems of Kühn and Osthus [Combinatorica 2009] and of Komlós [Combinatorica 2000]. Each of our results exhibits some curious, and perhaps unexpected, behaviour. Our solution to (i) makes use of a novel absorbing argument.
登录
查看更多内容
图中的三角度和三图中的四面体覆盖
DOI：
10.1017/s0963548320000061
发表时间：
2021
期刊：
Probability and Computing
影响因子：
--
作者：
Falgas-Ravry, Victor;Markström, Klas;Zhao, Yi
通讯作者：
Zhao, Yi
DOI：
10.1016/j.jctb.2016.06.007
发表时间：
2014-10
期刊：
J. Comb. Theory B
影响因子：
--
作者：
D. Conlon;J. Fox;Choongbum Lee;B. Sudakov
通讯作者：
D. Conlon;J. Fox;Choongbum Lee;B. Sudakov
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus
正分数 Erdos - 塞克雷斯定理
影响因子：
0.8
作者：
I. Bárány;P. Valtr
通讯作者：
P. Valtr
DOI：
10.37236/7816
发表时间：
2013-10
期刊：
Electron. J. Comb.
影响因子：
--
作者：
M. Balko;Josef Cibulka;Karel Král;J. Kynčl
通讯作者：
M. Balko;Josef Cibulka;Karel Král;J. Kynčl