Tiling Dense Hypergraphs

EUROCOMB’23

Abstract
There are three essentially necessary conditions for perfect tilings in hypergraphs, which correspond to barriers in space, divisibility and covering. It is natural to ask when these conditions are asymptotically sufficient. Our main result confirms this for hypergraph families that are approximately closed under taking a typical induced subgraph of constant order. As an application, we recover and extend a series of well-known results for perfect tilings in hypergraphs and related settings involving vertex orderings and rainbow structures.

Pages:
702–707
References

Y. Cheng, J. Han, B. Wang, and G. Wang, Rainbow spanning structures in graph and hypergraph systems, arXiv:2105.10219 (2021).

L. Ding, J. Han, S. Sun, G. Wang, and W. Zhou, F -factors in quasi-random hypergraphs, arXiv:2108.10731 (2021).

P. Erdős, On extremal problems of graphs and generalized graphs, Israel Journal of Mathematics 2 (1964), 183-190.
https://doi.org/10.1007/BF02759942

A. Freschi and A. Treglown, Dirac-type results for tilings and coverings in ordered graphs, Forum Math. Sigma 10 (2022), e104.
https://doi.org/10.1017/fms.2022.92

J. Han, On perfect matchings in k-complexes, Int. Math. Res. Not. 2021 (2021), no. 11, 8741-8762.
https://doi.org/10.1093/imrn/rnz343

J. Han, C. Zang, and Y. Zhao, Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs, J. Combin. Theory Ser. A 149 (2017), 115-147.
https://doi.org/10.1016/j.jcta.2017.02.003

E. Hurley, F. Joos, and R. Lang, Sufficient conditions for perfect tilings, arXiv:2201.03944 (2022).

P. Keevash, The existence of designs, arXiv:1401.3665 (2014).

P. Keevash, Hypergraph matchings and designs, arXiv:1807.05752 (2018).

P. Keevash and R. Mycroft, A geometric theory for hypergraph matching, vol. 233, Amer. Math. Soc., 2015.
https://doi.org/10.1090/memo/1098

F. Knox and A. Treglown, Embedding spanning bipartite graphs of small bandwidth, Comb. Probab. Comput. 22 (2013), no. 1, 71-96.
https://doi.org/10.1017/S0963548312000417

J. Komlós, Tiling Turán theorems, Combinatorica 20 (2000), no. 2, 203-218.
https://doi.org/10.1007/s004930070020

D. Kühn and D. Osthus, Embedding large subgraphs into dense graphs, arXiv:0901.3541 (2009).
https://doi.org/10.1017/CBO9781107325975.007

D. Kühn and D. Osthus, The minimum degree threshold for perfect graph packings, Combinatorica 29 (2009), no. 1, 65-107.
https://doi.org/10.1007/s00493-009-2254-3

D. Kühn, D. Osthus, and A. Treglown, Hamiltonian degree sequences in digraphs, J. Combin. Theory Ser. B 100 (2010), no. 4, 367-380.
https://doi.org/10.1016/j.jctb.2009.11.004

R. Lang and N. Sanhueza-Matamala, On sufficient conditions for spanning substructures in dense graphs, to appear in Proc. Lond. Math. Soc. (2023).

A. Lo and K. Markström, F -factors in hypergraphs via absorption, Graphs Combin. 31 (2015), no. 3, 679-712.
https://doi.org/10.1007/s00373-014-1410-8

R. Montgomery, A. Müyesser, and Y. Pehova, Transversal factors and spanning trees, Adv. Comb. (2022), Paper No. 3, 25.
https://doi.org/10.19086/aic.2022.3

R. Mycroft, Packing k-partite k-uniform hypergraphs, J. Combin. Theory Ser. A 138 (2016), 60-132.
https://doi.org/10.1016/j.jcta.2015.09.007

V. Rödl, A. Ruciński, and E. Szemerédi, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116 (2009), no. 3, 613-636.
https://doi.org/10.1016/j.jcta.2008.10.002

M. Simonovits and E. Szemerédi, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Building Bridges II: Mathematics of László Lovász, Bolyai Society Mathematical Studies, 28. Springer, 2019, pp. 445-592.
https://doi.org/10.1007/978-3-662-59204-5_14

Y. Zhao, Recent advances on Dirac-type problems for hypergraphs, Recent trends in combinatorics, 2016, pp. 145-165.
https://doi.org/10.1007/978-3-319-24298-9_6

Metrics

0

Views

0

PDF views