A blow-up lemma for approximate decompositions

• Published in: Transactions of the American Mathematical Society 2019-04, Vol.371 (7), p.4655-4742
• Main Authors: KIM, JAEHOON, KÜHN, DANIELA, OSTHUS, DERYK, TYOMKYN, MYKHAYLO
• Format: Article
• Language: English
• ISSN: 0002-9947; 1088-6850
• DOI: 10.1090/tran/7411

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.