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

Pages (from-to) | 4655-4742 |

Number of pages | 88 |

Journal | Transactions of the American Mathematical Society |

Volume | 371 |

Issue number | 7 |

Early online date | 21 Dec 2018 |

DOIs | |

Publication status | Published - 1 Apr 2019 |

## ASJC Scopus subject areas

- Mathematics(all)
- Applied Mathematics