## 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

## Additional Information

**Stefan Ehard**- Affiliation: Institut für Optimierung und Operations Research, Universität Ulm, Germany
- MR Author ID: 1274858
- Email: stefan.ehard@uni-ulm.de
**Felix Joos**- Affiliation: Institut für Informatik, Universität Heidelberg, Germany
- MR Author ID: 973316
- ORCID: 0000-0002-8539-9641
- Email: joos@informatik.uni-heidelberg.de
- Received by editor(s): December 29, 2020
- Received by editor(s) in revised form: February 3, 2022
- Published electronically: August 16, 2022
- Additional Notes: The research leading to these results was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 428212407 (second author)
- © Copyright 2022 by the authors
- Journal: Trans. Amer. Math. Soc.
**375**(2022), 7035-7119 - MSC (2020): Primary 20J05, 18B40, 18N10, 19A22
- DOI: https://doi.org/10.1090/tran/8685