A BLOW-UP LEMMA FOR APPROXIMATE DECOMPOSITIONS

Cited 12 time in webofscience Cited 0 time in scopus
  • Hit : 80
  • Download : 0
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, ..., H-s are bounded degree n-vertex graphs with Sigma(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 K-n implies an approximate version of the tree packing conjecture of Gyarfas 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 Szemeredi's regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Komlos, Sarkozy, and Szemeredi to the setting of approximate decompositions.
Publisher
AMER MATHEMATICAL SOC
Issue Date
2019-04
Language
English
Article Type
Article
Citation

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, v.371, no.7, pp.4655 - 4742

ISSN
0002-9947
DOI
10.1090/tran/7411
URI
http://hdl.handle.net/10203/268271
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 12 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0