Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree

Ehard, Stefan; Joos, Felix

doi:10.1090/tran/8685

Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
HTML articles powered by AMS MathViewer

by Stefan Ehard and Felix Joos PDF

Trans. Amer. Math. Soc. 375 (2022), 7035-7119

Abstract:

We prove that any quasirandom uniform hypergraph $H$ can be approximately decomposed into any collection of bounded degree hypergraphs with almost as many edges. In fact, our results also apply to multipartite hypergraphs and even to the sparse setting when the density of $H$ quickly tends to $0$ in terms of the number of vertices of $H$. Our results answer and address questions of Kim, Kühn, Osthus and Tyomkyn; and Glock, Kühn and Osthus as well as Keevash.

The provided approximate decompositions exhibit strong quasirandom properties which are very useful for forthcoming applications. Our results also imply approximate solutions to natural hypergraph versions of long-standing graph decomposition problems, as well as several decomposition results for (quasi)random simplicial complexes into various more elementary simplicial complexes such as triangulations of spheres and other manifolds.

References

P. Allen, J. Böttcher, D. Clemens, J. Hladký, D. Piguet, and A. Taraz, The tree packing conjecture for trees of almost linear maximum degree, arXiv:2106.11720, 2021.
P. Allen, J. Böttcher, D. Clemens, and A. Taraz, Perfectly packing graphs with bounded degeneracy and many leaves, Israel J. Math., To appear.
P. Allen, J. Böttcher, H. Hàn, Y. Kohayakawa, and Y. Person, Blow-up lemmas for sparse graphs, arXiv:1612.00622, 2016.
Peter Allen, Julia Böttcher, Jan Hladký, and Diana Piguet, Packing degenerate graphs, Adv. Math. 354 (2019), 106739, 58. MR 3988639, DOI 10.1016/j.aim.2019.106739
Peter Allen, Julia Böttcher, Jozef Skokan, and Maya Stein, Regularity inheritance in pseudorandom graphs, Random Structures Algorithms 56 (2020), no. 2, 306–338. MR 4060348, DOI 10.1002/rsa.20851
Noga Alon, Vojtech Rödl, and Andrzej Ruciński, Perfect matchings in $\epsilon$-regular graphs, Electron. J. Combin. 5 (1998), Research Paper 13, 4. MR 1604533
Robert F. Bailey and Brett Stevens, Hamiltonian decompositions of complete $k$-uniform hypergraphs, Discrete Math. 310 (2010), no. 22, 3088–3095. MR 2684077, DOI 10.1016/j.disc.2009.03.047
Deepak Bal and Alan Frieze, Packing tight Hamilton cycles in uniform hypergraphs, SIAM J. Discrete Math. 26 (2012), no. 2, 435–451. MR 2967475, DOI 10.1137/11082378X
Zsolt Baranyai, The edge-coloring of complete hypergraphs. I, J. Combin. Theory Ser. B 26 (1979), no. 3, 276–294. MR 535941, DOI 10.1016/0095-8956(79)90002-9
Julia Böttcher, Jan Hladký, Diana Piguet, and Anusch Taraz, An approximate version of the tree packing conjecture, Israel J. Math. 211 (2016), no. 1, 391–446. MR 3474969, DOI 10.1007/s11856-015-1277-2
Fan Chung and Ronald Graham, Sparse quasi-random graphs, Combinatorica 22 (2002), no. 2, 217–244. Special issue: Paul Erdős and his mathematics. MR 1909084, DOI 10.1007/s004930200010
S. Ehard, Embeddings and decompositions of graphs and hypergraphs, Ph.D. Thesis, 2020.
Stefan Ehard, Stefan Glock, and Felix Joos, Pseudorandom hypergraph matchings, Combin. Probab. Comput. 29 (2020), no. 6, 868–885. MR 4173135, DOI 10.1017/s0963548320000280
Đinh Quang Lu’u, A short proof of biting lemma, Sém. Anal. Convexe 19 (1989), Exp. No. 1, 13. MR 1061746
Asaf Ferber, Choongbum Lee, and Frank Mousset, Packing spanning graphs from separable families, Israel J. Math. 219 (2017), no. 2, 959–982. MR 3649613, DOI 10.1007/s11856-017-1504-0
David A. Freedman, On tail probabilities for martingales, Ann. Probability 3 (1975), 100–118. MR 380971, DOI 10.1214/aop/1176996452
Alan Frieze and Michael Krivelevich, Packing Hamilton cycles in random and pseudo-random hypergraphs, Random Structures Algorithms 41 (2012), no. 1, 1–22. MR 2943424, DOI 10.1002/rsa.20396
Alan Frieze, Michael Krivelevich, and Po-Shen Loh, Packing tight Hamilton cycles in 3-uniform hypergraphs, Random Structures Algorithms 40 (2012), no. 3, 269–300. MR 2900140, DOI 10.1002/rsa.20374
Agelos Georgakopoulos, John Haslegrave, Richard Montgomery, and Bhargav Narayanan, Spanning surfaces in 3-graphs, J. Eur. Math. Soc. (JEMS) 24 (2022), no. 1, 303–339. MR 4375452, DOI 10.4171/jems/1101
Stefan Glock, Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus, Resolution of the Oberwolfach problem, J. Eur. Math. Soc. (JEMS) 23 (2021), no. 8, 2511–2547. MR 4269420, DOI 10.4171/jems/1060
S. Glock, D. Kühn, A. Lo, and D. Osthus, The existence of designs via iterative absorption: hypergraph $F$-designs for arbitrary $F$, Mem. Amer. Math. Soc., To appear.
Stefan Glock, Daniela Kühn, and Deryk Osthus, Extremal aspects of graph and hypergraph decomposition problems, Surveys in combinatorics 2021, London Math. Soc. Lecture Note Ser., vol. 470, Cambridge Univ. Press, Cambridge, 2021, pp. 235–265. MR 4273432
Hiệp Hàn, Jie Han, and Patrick Morris, Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2020, pp. 702–717. MR 4141225
Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus, Optimal packings of bounded degree trees, J. Eur. Math. Soc. (JEMS) 21 (2019), no. 12, 3573–3647. MR 4022711, DOI 10.4171/JEMS/909
F. Joos and M. Kühn, Fractional cycle decompositions in hypergraphs, arXiv:2101.05526, 2021.
Peter Keevash, A hypergraph blow-up lemma, Random Structures Algorithms 39 (2011), no. 3, 275–376. MR 2816936, DOI 10.1002/rsa.20362
Peter Keevash, The existence of designs, arXiv:1401.3665, 2014.
Peter Keevash, The existence of designs II, arXiv:1802.05900, 2018.
Peter Keevash, Hypergraph matchings and designs, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3113–3135. MR 3966525
P. Keevash and K. Staden, Ringel’s tree packing conjecture in quasirandom graphs, arXiv:2004.09947, 2020.
Peter Keevash and Katherine Staden, The generalised Oberwolfach problem, J. Combin. Theory Ser. B 152 (2022), 281–318. MR 4332743, DOI 10.1016/j.jctb.2021.09.007
Jaehoon Kim, Daniela Kühn, Deryk Osthus, and Mykhaylo Tyomkyn, A blow-up lemma for approximate decompositions, Trans. Amer. Math. Soc. 371 (2019), no. 7, 4655–4742. MR 3934464, DOI 10.1090/tran/7411
János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Blow-up lemma, Combinatorica 17 (1997), no. 1, 109–123. MR 1466579, DOI 10.1007/BF01196135
Nathan Linial and Roy Meshulam, Homological connectivity of random 2-complexes, Combinatorica 26 (2006), no. 4, 475–487. MR 2260850, DOI 10.1007/s00493-006-0027-9
Nathan Linial and Yuval Peled, On the phase transition in random simplicial complexes, Ann. of Math. (2) 184 (2016), no. 3, 745–773. MR 3549622, DOI 10.4007/annals.2016.184.3.3
Zur Luria and Ran J. Tessler, A sharp threshold for spanning 2-spheres in random 2-complexes, Proc. Lond. Math. Soc. (3) 119 (2019), no. 3, 733–780. MR 3960667, DOI 10.1112/plms.12247
Colin McDiarmid, On the method of bounded differences, Surveys in combinatorics, 1989 (Norwich, 1989) London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148–188. MR 1036755
Silvia Messuti, Vojtěch Rödl, and Mathias Schacht, Packing minor-closed families of graphs into complete graphs, J. Combin. Theory Ser. B 119 (2016), 245–265. MR 3486345, DOI 10.1016/j.jctb.2016.03.003
R. Montgomery, A. Pokrovskiy, and B. Sudakov, A proof of Ringel’s conjecture, Geom. Funct. Anal. 31 (2021), no. 3, 663–720. MR 4311581, DOI 10.1007/s00039-021-00576-2
Vojtech Rödl and Andrzej Ruciński, Perfect matchings in $\epsilon$-regular graphs and the blow-up lemma, Combinatorica 19 (1999), no. 3, 437–452. MR 1723256, DOI 10.1007/s004930050063
Andrew Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985) North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, pp. 307–331. MR 930498
Andrew Thomason, Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 173–195. MR 905280
Richard M. Wilson, An existence theory for pairwise balanced designs. I. Composition theorems and morphisms, J. Combinatorial Theory Ser. A 13 (1972), 220–245. MR 304203, DOI 10.1016/0097-3165(72)90028-3
Richard M. Wilson, An existence theory for pairwise balanced designs. II. The structure of PBD-closed sets and the existence conjectures, J. Combinatorial Theory Ser. A 13 (1972), 246–273. MR 304204, DOI 10.1016/0097-3165(72)90029-5
Richard M. Wilson, An existence theory for pairwise balanced designs. III. Proof of the existence conjectures, J. Combinatorial Theory Ser. A 18 (1975), 71–79. MR 366695, DOI 10.1016/0097-3165(75)90067-9