A blow-up lemma for approximate decompositions

Jaehoon Kim, Daniela Kuhn, Deryk Osthus, Mykhaylo Tyomkyn

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)
156 Downloads (Pure)


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 H1,…, Hs are bounded degree n-vertex graphs with Σ s i=1 e(H i ) ≤ (1 - o(1))e(G). Then H 1 ,…, H s can be packed edge-disjointly into G. The case when G is the complete graph Kn 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.

Original languageEnglish
Pages (from-to)4655-4742
Number of pages88
JournalTransactions of the American Mathematical Society
Issue number7
Early online date21 Dec 2018
Publication statusPublished - 1 Apr 2019

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics


Dive into the research topics of 'A blow-up lemma for approximate decompositions'. Together they form a unique fingerprint.

Cite this