A blow-up lemma for approximate decompositions
HTML articles powered by AMS MathViewer
- by Jaehoon Kim, Daniela Kühn, Deryk Osthus and Mykhaylo Tyomkyn PDF
- Trans. Amer. Math. Soc. 371 (2019), 4655-4742 Request permission
Abstract:
We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to long-standing decomposition problems. For instance, our results imply the following. Let $G$ be a quasi-random $n$-vertex graph and suppose $H_1,\dots ,H_s$ are bounded degree $n$-vertex graphs with $\sum _{i=1}^{s} e(H_i) \leq (1-o(1)) e(G)$. Then $H_1,\dots ,H_s$ can be packed edge-disjointly into $G$. The case when $G$ is the complete graph $K_n$ implies an approximate version of the tree packing conjecture of Gyárfás and Lehel for bounded degree trees, and of the Oberwolfach problem.
We provide a more general version of the above approximate decomposition result which can be applied to super-regular graphs and thus can be combined with Szemerédi’s regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Komlós, Sárkőzy, and Szemerédi to the setting of approximate decompositions.
References
- N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), no. 1, 80–109. MR 1251840, DOI 10.1006/jagm.1994.1005
- 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
- Noga Alon and Raphael Yuster, Every $H$-decomposition of $K_n$ has a nearly resolvable alternative, European J. Combin. 21 (2000), no. 7, 839–845. MR 1787897, DOI 10.1006/eujc.2000.0400
- József Balogh and Cory Palmer, On the tree packing conjecture, SIAM J. Discrete Math. 27 (2013), no. 4, 1995–2006. MR 3131474, DOI 10.1137/120902719
- 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
- Béla Bollobás, Some remarks on packing trees, Discrete Math. 46 (1983), no. 2, 203–204. MR 710892, DOI 10.1016/0012-365X(83)90254-6
- Béla Bollobás, Alexandr Kostochka, and Kittikorn Nakprasit, Packing $d$-degenerate graphs, J. Combin. Theory Ser. B 98 (2008), no. 1, 85–94. MR 2368025, DOI 10.1016/j.jctb.2007.05.002
- 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
- Julia Böttcher, Mathias Schacht, and Anusch Taraz, Proof of the bandwidth conjecture of Bollobás and Komlós, Math. Ann. 343 (2009), no. 1, 175–205. MR 2448444, DOI 10.1007/s00208-008-0268-6
- Darryn Bryant, Daniel Horsley, and William Pettersson, Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, Proc. Lond. Math. Soc. (3) 108 (2014), no. 5, 1153–1192. MR 3214677, DOI 10.1112/plms/pdt051
- Darryn Bryant and Victor Scharaschkin, Complete solutions to the Oberwolfach problem for an infinite set of orders, J. Combin. Theory Ser. B 99 (2009), no. 6, 904–918. MR 2558441, DOI 10.1016/j.jctb.2009.03.003
- B. Csaba, On the Bollobás-Eldridge conjecture for bipartite graphs, Combin. Probab. Comput. 16 (2007), no. 5, 661–691. MR 2346807, DOI 10.1017/S0963548307008395
- Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, and Andrew Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures, Mem. Amer. Math. Soc. 244 (2016), no. 1154, v+164. MR 3545109, DOI 10.1090/memo/1154
- J. H. Dinitz and Alan C. H. Ling, The Hamilton-Waterloo problem: the case of triangle-factors and one Hamilton cycle, J. Combin. Des. 17 (2009), no. 2, 160–176. MR 2489441, DOI 10.1002/jcd.20196
- Edward Dobson, Packing trees into the complete graph, Combin. Probab. Comput. 11 (2002), no. 3, 263–272. MR 1909502, DOI 10.1017/S0963548301005077
- Richard A. Duke, Hanno Lefmann, and Vojtěch Rödl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM J. Comput. 24 (1995), no. 3, 598–620. MR 1333857, DOI 10.1137/S0097539793247634
- 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
- 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
- A. Ferber and W. Samotij, Packing trees of unbounded degrees in random graphs, preprint, arxiv:1607.07342 (2016).
- S. Glock, D. Kühn, A. Lo, and D. Osthus, The existence of designs via iterative absorption, preprint, arXiv:1611.06827 (2016).
- S. Glock, D. Kühn, A. Lo, and D. Osthus, Hypergraph $F$-designs for arbitrary $F$, preprint arXiv:1706.01800 (2017).
- Stefan Glock, Daniela Kühn, and Deryk Osthus, Optimal path and cycle decompositions of dense quasirandom graphs, J. Combin. Theory Ser. B 118 (2016), 88–108. MR 3471846, DOI 10.1016/j.jctb.2016.01.004
- A. Gyárfás and J. Lehel, Packing trees of different order into $K_{n}$, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976) Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, 1978, pp. 463–469. MR 519284
- A. Hajnal and E. Szemerédi, Proof of a conjecture of P. Erdős, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969) North-Holland, Amsterdam, 1970, pp. 601–623. MR 0297607
- Arthur M. Hobbs, Brian A. Bourgeois, and Jothi Kasiraj, Packing trees in complete graphs, Discrete Math. 67 (1987), no. 1, 27–42. MR 908184, DOI 10.1016/0012-365X(87)90164-6
- F. Joos, J. Kim, D. Kühn and D. Osthus, Optimal packings of bounded degree trees, preprint, arXiv:1606.03953 (2016).
- 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, preprint, arXiv:1401.3665 (2014).
- 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
- János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Proof of the Seymour conjecture for large graphs, Ann. Comb. 2 (1998), no. 1, 43–60. MR 1682919, DOI 10.1007/BF01626028
- János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Spanning trees in dense graphs, Combin. Probab. Comput. 10 (2001), no. 5, 397–416. MR 1869048, DOI 10.1017/S0963548301004849
- János Komlós, Gábor N. Sárközy, and Endre Szemerédi, Proof of the Alon-Yuster conjecture, Discrete Math. 235 (2001), no. 1-3, 255–269. Combinatorics (Prague, 1998). MR 1829855, DOI 10.1016/S0012-365X(00)00279-X
- Daniela Kühn and Deryk Osthus, The minimum degree threshold for perfect graph packings, Combinatorica 29 (2009), no. 1, 65–107. MR 2506388, DOI 10.1007/s00493-009-2254-3
- Daniela Kühn and Deryk Osthus, Embedding large subgraphs into dense graphs, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge Univ. Press, Cambridge, 2009, pp. 137–167. MR 2588541
- 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
- Daniela Kühn and Deryk Osthus, Hamilton decompositions of regular expanders: applications, J. Combin. Theory Ser. B 104 (2014), 1–27. MR 3132742, DOI 10.1016/j.jctb.2013.10.006
- 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
- 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, Survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam, 1973, pp. 361–375. MR 0360311
- Y. Roditty, Packing and covering of the complete graph. III. On the tree packing conjecture, Sci. Ser. A Math. Sci. (N.S.) 1 (1988), 81–85. MR 2313052
- 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
- Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
- 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
- Andrzej Żak, Packing large trees of consecutive orders, Discrete Math. 340 (2017), no. 2, 252–263. MR 3578822, DOI 10.1016/j.disc.2016.07.022
Additional Information
- Jaehoon Kim
- Affiliation: School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom
- Address at time of publication: Mathematics Institute, University of Warwick, Coventry, CV4 7AL, United Kingdom
- MR Author ID: 973739
- Email: Jaehoon.Kim.1@warwick.ac.uk; mutualteon@gmail.com
- Daniela Kühn
- Affiliation: School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom
- MR Author ID: 652464
- Email: d.kuhn@bham.ac.uk
- Deryk Osthus
- Affiliation: School of Mathematics, University of Birmingham, Edgbaston, Birmingham, B15 2TT, United Kingdom
- MR Author ID: 659284
- Email: d.osthus@bham.ac.uk
- Mykhaylo Tyomkyn
- Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel
- Address at time of publication: Mathematical Institute, University of Oxford, Oxford, OX2 6GG, United Kingdom
- MR Author ID: 884018
- Email: tyomkyn@maths.ox.ac.uk
- Received by editor(s): April 25, 2016
- Received by editor(s) in revised form: July 16, 2017
- Published electronically: December 21, 2018
- Additional Notes: The research leading to these results was partially supported by the EPSRC, grant no. EP/M009408/1 (second and third authors), and by the Royal Society and the Wolfson Foundation (second author). The research was also partially supported by the European Research Council under the European Union’s Seventh Framework Programme (FP/2007–2013) / ERC Grant 306349 (first, third, and fourth authors).
- © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 4655-4742
- MSC (2010): Primary 05C35, 05C70; Secondary 05D40, 05B40, 05C80
- DOI: https://doi.org/10.1090/tran/7411
- MathSciNet review: 3934464