AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
The Existence of Designs via Iterative Absorption: Hypergraph $F$-designs for Arbitrary $F$
About this Title
Stefan Glock, Daniela Kühn, Allan Lo and Deryk Osthus
Publication: Memoirs of the American Mathematical Society
Publication Year:
2023; Volume 284, Number 1406
ISBNs: 978-1-4704-6024-2 (print); 978-1-4704-7444-7 (online)
DOI: https://doi.org/10.1090/memo/1406
Published electronically: March 21, 2023
Keywords: Block designs,
decomposition,
iterative absorption
Table of Contents
Chapters
- 1. Introduction
- 2. Notation
- 3. Outline of the methods
- 4. Decompositions of supercomplexes
- 5. Tools
- 6. Nibbles, boosting and greedy covers
- 7. Vortices
- 8. Absorbers
- 9. Proof of the main theorems
- 10. Covering down
- 11. Achieving divisibility
- 12. Recent developments
Abstract
We solve the existence problem for $F$-designs for arbitrary $r$-uniform hypergraphs $F$. This implies that given any $r$-uniform hypergraph $F$, the trivially necessary divisibility conditions are sufficient to guarantee a decomposition of any sufficiently large complete $r$-uniform hypergraph into edge-disjoint copies of $F$, which answers a question asked e.g. by Keevash. The graph case $r=2$ was proved by Wilson in 1975 and forms one of the cornerstones of design theory. The case when $F$ is complete corresponds to the existence of block designs, a problem going back to the 19th century, which was recently settled by Keevash. In particular, our argument provides a new proof of the existence of block designs, based on iterative absorption (which employs purely probabilistic and combinatorial methods).
Our main result concerns decompositions of hypergraphs whose clique distribution fulfills certain regularity constraints. Our argument allows us to employ a ‘regularity boosting’ process which frequently enables us to satisfy these constraints even if the clique distribution of the original hypergraph does not satisfy them. This enables us to go significantly beyond the setting of quasirandom hypergraphs considered by Keevash. In particular, we obtain a resilience version and a decomposition result for hypergraphs of large minimum degree.
- Noga Alon, Jeong-Han Kim, and Joel Spencer, Nearly perfect matchings in regular simple hypergraphs, Israel J. Math. 100 (1997), 171–187. MR 1469109, DOI 10.1007/BF02773639
- Noga Alon and Raphael Yuster, On a hypergraph matching problem, Graphs Combin. 21 (2005), no. 4, 377–384. MR 2209008, DOI 10.1007/s00373-005-0628-x
- Dan Archdeacon, Self-dual embeddings of complete multipartite graphs, J. Graph Theory 18 (1994), no. 7, 735–749. MR 1297194, DOI 10.1002/jgt.3190180709
- Zs. Baranyai, On the factorization of the complete uniform hypergraph, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 91–108. MR 0416986
- Ben Barber, Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, and Deryk Osthus, Minimalist designs, Random Structures Algorithms 57 (2020), no. 1, 47–63. MR 4120592, DOI 10.1002/rsa.20915
- Ben Barber, Daniela Kühn, Allan Lo, Richard Montgomery, and Deryk Osthus, Fractional clique decompositions of dense graphs and hypergraphs, J. Combin. Theory Ser. B 127 (2017), 148–186. MR 3704659, DOI 10.1016/j.jctb.2017.05.005
- Ben Barber, Daniela Kühn, Allan Lo, and Deryk Osthus, Edge-decompositions of graphs with high minimum degree, Adv. Math. 288 (2016), 337–385. MR 3436388, DOI 10.1016/j.aim.2015.09.032
- Ben Barber, Daniela Kühn, Allan Lo, Deryk Osthus, and Amelia Taylor, Clique decompositions of multipartite graphs and completion of Latin squares, J. Combin. Theory Ser. A 151 (2017), 146–201. MR 3663493, DOI 10.1016/j.jcta.2017.04.005
- J. Blömer, M. Kalfane, R. Karp, M. Karpinski, M. Luby, D. Zuckerman, An XOR-based erasure-resilient coding scheme, TR-95-048, International Computer Science Institute, 1995.
- Flora C. Bowditch and Peter J. Dukes, Fractional triangle decompositions of dense 3-partite graphs, J. Comb. 10 (2019), no. 2, 255–282. MR 3912215, DOI 10.4310/JOC.2019.v10.n2.a5
- Darryn Bryant and Daniel Horsley, A proof of Lindner’s conjecture on embeddings of partial Steiner triple systems, J. Combin. Des. 17 (2009), no. 1, 63–89. MR 2475426, DOI 10.1002/jcd.20189
- A.L. Cauchy, Exercices d’analyse et de physique mathematique 2, 2nd edition, Bachelier, Paris, 1841.
- C.J. Colbourn and J.H. Dinitz, Handbook of Combinatorial Designs, 2nd edition, CRC Press, 2006.
- François Dross, Fractional triangle decompositions in graphs with large minimum degree, SIAM J. Discrete Math. 30 (2016), no. 1, 36–42. MR 3440184, DOI 10.1137/15M1014310
- Peter Dukes and Alan C. H. Ling, Asymptotic existence of resolvable graph designs, Canad. Math. Bull. 50 (2007), no. 4, 504–518. MR 2364201, DOI 10.4153/CMB-2007-050-x
- P. Erdős and H. Hanani, On a limit theorem in combinatorial analysis, Publ. Math. Debrecen 10 (1963), 10–13. MR 166116, DOI 10.5486/pmd.1963.10.1-4.02
- Asaf Ferber, Rani Hod, Michael Krivelevich, and Benny Sudakov, A construction of almost Steiner systems, J. Combin. Des. 22 (2014), no. 11, 488–494. MR 3263662, DOI 10.1002/jcd.21380
- Stefan Glock, Felix Joos, Daniela Kühn, and Deryk Osthus, Euler tours in hypergraphs, Combinatorica 40 (2020), no. 5, 679–690. MR 4181762, DOI 10.1007/s00493-020-4046-8
- Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, and Deryk Osthus, On the decomposition threshold of a given graph, J. Combin. Theory Ser. B 139 (2019), 47–127. MR 4010186, DOI 10.1016/j.jctb.2019.02.010
- Hiệp Hàn, Yury Person, and Mathias Schacht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math. 23 (2009), no. 2, 732–748. MR 2496914, DOI 10.1137/080729657
- Haim Hanani, Decomposition of hypergraphs into octahedra, Second International Conference on Combinatorial Mathematics (New York, 1978) Ann. New York Acad. Sci., vol. 319, New York Acad. Sci., New York, 1979, pp. 260–264. MR 556032
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
- P. Keevash, The existence of designs, arXiv:1401.3665, 2014.
- Peter Keevash, Counting designs, J. Eur. Math. Soc. (JEMS) 20 (2018), no. 4, 903–927. MR 3779688, DOI 10.4171/JEMS/779
- P. Keevash, The existence of designs II, arXiv:1802.05900, 2018.
- T.P. Kirkman, On a problem in combinatorics, Cambridge Dublin Math. J. 2 (1847), 191–204.
- Fiachra Knox, Daniela Kühn, and Deryk Osthus, Edge-disjoint Hamilton cycles in random graphs, Random Structures Algorithms 46 (2015), no. 3, 397–445. MR 3324754, DOI 10.1002/rsa.20510
- Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraëte, On independent sets in hypergraphs, Random Structures Algorithms 44 (2014), no. 2, 224–239. MR 3158630, DOI 10.1002/rsa.20453
- Michael Krivelevich, Triangle factors in random graphs, Combin. Probab. Comput. 6 (1997), no. 3, 337–347. MR 1464569, DOI 10.1017/S0963548397003106
- Daniela Kühn and Deryk Osthus, Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments, Adv. Math. 237 (2013), 62–146. MR 3028574, DOI 10.1016/j.aim.2013.01.005
- Greg Kuperberg, Shachar Lovett, and Ron Peled, Probabilistic existence of regular combinatorial structures, Geom. Funct. Anal. 27 (2017), no. 4, 919–972. MR 3678505, DOI 10.1007/s00039-017-0416-9
- Matthew Kwan, Almost all Steiner triple systems have perfect matchings, Proc. Lond. Math. Soc. (3) 121 (2020), no. 6, 1468–1495. MR 4144368, DOI 10.1112/plms.12373
- Nathan Linial and Zur Luria, An upper bound on the number of Steiner triple systems, Random Structures Algorithms 43 (2013), no. 4, 399–406. MR 3124689, DOI 10.1002/rsa.20487
- Shachar Lovett, Sankeerth Rao, and Alexander Vardy, Probabilistic existence of large sets of designs, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2018, pp. 1545–1556. MR 3775889, DOI 10.1137/1.9781611975031.101
- Richard Montgomery, Fractional clique decompositions of dense partite graphs, Combin. Probab. Comput. 26 (2017), no. 6, 911–943. MR 3714998, DOI 10.1017/S0963548317000165
- C.St.J.A. Nash-Williams, An unsolved problem concerning decomposition of graphs into triangles, In: Combinatorial Theory and its Applications III, pages 1179–1183, North Holland, 1970.
- Nicholas Pippenger and Joel Spencer, Asymptotic behavior of the chromatic index for hypergraphs, J. Combin. Theory Ser. A 51 (1989), no. 1, 24–42. MR 993646, DOI 10.1016/0097-3165(89)90074-5
- Rajeev Raman, The power of collision: randomized parallel algorithms for chaining and integer sorting, Foundations of software technology and theoretical computer science (Bangalore, 1990) Lecture Notes in Comput. Sci., vol. 472, Springer, Berlin, 1990, pp. 161–175. MR 1085044, DOI 10.1007/3-540-53487-3_{4}2
- D. K. Ray-Chaudhuri and Richard M. Wilson, The existence of resolvable block designs, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam, 1973, pp. 361–375. MR 0360311
- Vojtěch Rödl, On a packing and covering problem, European J. Combin. 6 (1985), no. 1, 69–78. MR 793489, DOI 10.1016/S0195-6698(85)80023-8
- Vojtech Rödl and Andrzej Ruciński, Dirac-type questions for hypergraphs—a survey (or more problems for Endre to solve), An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 561–590. MR 2815614, DOI 10.1007/978-3-642-14444-8_{1}6
- Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi, A Dirac-type theorem for 3-uniform hypergraphs, Combin. Probab. Comput. 15 (2006), no. 1-2, 229–251. MR 2195584, DOI 10.1017/S0963548305007042
- Vojtěch Rödl and Edita Šiňajová, Note on independent sets in Steiner systems, Proceedings of the Fifth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science (Poznań, 1991), 1994, pp. 183–190. MR 1248185, DOI 10.1002/rsa.3240050117
- Samuel Schechter, On the inversion of certain matrices, Math. Tables Aids Comput. 13 (1959), 73–77. MR 105798, DOI 10.1090/S0025-5718-1959-0105798-2
- Luc Teirlinck, Nontrivial $t$-designs without repeated blocks exist for all $t$, Discrete Math. 65 (1987), no. 3, 301–311. MR 897654, DOI 10.1016/0012-365X(87)90061-6
- Van H. Vu, New bounds on nearly perfect matchings in hypergraphs: higher codegrees do help, Random Structures Algorithms 17 (2000), no. 1, 29–63. MR 1768848, DOI 10.1002/1098-2418(200008)17:1<29::AID-RSA4>3.0.CO;2-W
- 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
- Richard M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 647–659. MR 0396347
- Raphael Yuster, Decomposing hypergraphs into simple hypertrees, Combinatorica 20 (2000), no. 1, 119–140. MR 1770531, DOI 10.1007/s004930070036
- R. Yuster, Combinatorial and computational aspects of graph packing and graph decomposition, Computer Science Review 1 (2007), 12–26.
- Yi Zhao, Recent advances on Dirac-type problems for hypergraphs, Recent trends in combinatorics, IMA Vol. Math. Appl., vol. 159, Springer, [Cham], 2016, pp. 145–165. MR 3526407, DOI 10.1007/978-3-319-24298-9_{6}