A blow-up lemma for approximate decompositions
| Autor: | Mykhaylo Tyomkyn, Jaehoon Kim, Daniela Kühn, Deryk Osthus |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Transactions of the American Mathematical Society. 371:4655-4742 |
| ISSN: | 1088-6850 0002-9947 |
| DOI: | 10.1090/tran/7411 |
| Popis: | 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 G be a quasi-random n n -vertex graph and suppose H 1 , … , H s H_1,\dots ,H_s are bounded degree n n -vertex graphs with ∑ i = 1 s e ( H i ) ≤ ( 1 − o ( 1 ) ) e ( G ) \sum _{i=1}^{s} e(H_i) \leq (1-o(1)) e(G) . Then H 1 , … , H s H_1,\dots ,H_s can be packed edge-disjointly into G G . The case when G G is the complete graph K n 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|