Cover Image

Optimal packings of bounded degree trees

We prove that if $T_1,\dots, T_n$ is a sequence of bounded degree trees so that $T_i$ has $i$ vertices, then $K_n$ has a decomposition into $T_1,\dots, T_n$. This shows that the tree packing conjecture of Gy\'arf\'as and Lehel from 1976 holds for all bounded degree trees (in fact, we can a...

Full description

Saved in:
Bibliographic Details
Main Authors: Joos, Felix (Author) , Kim, Jaehoon (Author) , Kühn, Daniela (Author) , Osthus, Deryk (Author)
Format: Article (Journal) Chapter/Article
Language:English
Published: 13 Jun 2016
In: Arxiv
Year: 2016, Pages: 1-56
DOI:10.48550/arXiv.1606.03953
Online Access:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.48550/arXiv.1606.03953
Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/1606.03953
Get full text
Author Notes:Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus

MARC

LEADER 00000caa a2200000 c 4500
001 1810692040
003 DE-627
005 20220820224209.0
007 cr uuu---uuuuu
008 220718s2016 xx |||||o 00| ||eng c
024 7 |a 10.48550/arXiv.1606.03953  |2 doi 
035 |a (DE-627)1810692040 
035 |a (DE-599)KXP1810692040 
035 |a (OCoLC)1341463886 
040 |a DE-627  |b ger  |c DE-627  |e rda 
041 |a eng 
084 |a 29  |2 sdnb 
100 1 |a Joos, Felix  |d 1989-  |e VerfasserIn  |0 (DE-588)1075006171  |0 (DE-627)832846244  |0 (DE-576)442747438  |4 aut 
245 1 0 |a Optimal packings of bounded degree trees  |c Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus 
264 1 |c 13 Jun 2016 
300 |a 56 
336 |a Text  |b txt  |2 rdacontent 
337 |a Computermedien  |b c  |2 rdamedia 
338 |a Online-Ressource  |b cr  |2 rdacarrier 
500 |a Identifizierung der Ressource nach: 13 Mar 2019 
500 |a Gesehen am 27.07.2022 
520 |a We prove that if $T_1,\dots, T_n$ is a sequence of bounded degree trees so that $T_i$ has $i$ vertices, then $K_n$ has a decomposition into $T_1,\dots, T_n$. This shows that the tree packing conjecture of Gy\'arf\'as and Lehel from 1976 holds for all bounded degree trees (in fact, we can allow the first $o(n)$ trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture from 1963 holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemer\'{e}di's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions. 
650 4 |a Mathematics - Combinatorics 
700 1 |a Kim, Jaehoon  |e VerfasserIn  |0 (DE-588)1262517826  |0 (DE-627)1810217857  |4 aut 
700 1 |a Kühn, Daniela  |d 1973-  |e VerfasserIn  |0 (DE-588)123412005  |0 (DE-627)082540500  |0 (DE-576)293697906  |4 aut 
700 1 |a Osthus, Deryk  |d 1974-  |e VerfasserIn  |0 (DE-588)12285702X  |0 (DE-627)08219744X  |0 (DE-576)293449856  |4 aut 
773 0 8 |i Enthalten in  |t Arxiv  |d Ithaca, NY : Cornell University, 1991  |g (2016), Artikel-ID 1606.03953, Seite 1-56  |h Online-Ressource  |w (DE-627)509006531  |w (DE-600)2225896-6  |w (DE-576)28130436X  |7 nnas  |a Optimal packings of bounded degree trees 
773 1 8 |g year:2016  |g elocationid:1606.03953  |g pages:1-56  |g extent:56  |a Optimal packings of bounded degree trees 
856 4 0 |u https://doi.org/10.48550/arXiv.1606.03953  |x Verlag  |x Resolving-System  |z lizenzpflichtig  |3 Volltext 
856 4 0 |u http://arxiv.org/abs/1606.03953  |x Verlag  |z lizenzpflichtig  |3 Volltext 
951 |a AR 
992 |a 20220718 
993 |a Article 
994 |a 2016 
998 |g 1075006171  |a Joos, Felix  |m 1075006171:Joos, Felix  |p 1  |x j 
999 |a KXP-PPN1810692040  |e 4169389794 
BIB |a Y 
JSO |a {"person":[{"roleDisplay":"VerfasserIn","display":"Joos, Felix","role":"aut","family":"Joos","given":"Felix"},{"role":"aut","display":"Kim, Jaehoon","roleDisplay":"VerfasserIn","given":"Jaehoon","family":"Kim"},{"given":"Daniela","family":"Kühn","role":"aut","roleDisplay":"VerfasserIn","display":"Kühn, Daniela"},{"display":"Osthus, Deryk","roleDisplay":"VerfasserIn","role":"aut","family":"Osthus","given":"Deryk"}],"title":[{"title":"Optimal packings of bounded degree trees","title_sort":"Optimal packings of bounded degree trees"}],"recId":"1810692040","language":["eng"],"note":["Identifizierung der Ressource nach: 13 Mar 2019","Gesehen am 27.07.2022"],"type":{"bibl":"chapter","media":"Online-Ressource"},"name":{"displayForm":["Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus"]},"id":{"doi":["10.48550/arXiv.1606.03953"],"eki":["1810692040"]},"origin":[{"dateIssuedKey":"2016","dateIssuedDisp":"13 Jun 2016"}],"relHost":[{"titleAlt":[{"title":"Arxiv.org"},{"title":"Arxiv.org e-print archive"},{"title":"Arxiv e-print archive"},{"title":"De.arxiv.org"}],"part":{"pages":"1-56","year":"2016","extent":"56","text":"(2016), Artikel-ID 1606.03953, Seite 1-56"},"pubHistory":["1991 -"],"language":["eng"],"recId":"509006531","disp":"Optimal packings of bounded degree treesArxiv","type":{"bibl":"edited-book","media":"Online-Ressource"},"note":["Gesehen am 28.05.2024"],"title":[{"title_sort":"Arxiv","title":"Arxiv"}],"physDesc":[{"extent":"Online-Ressource"}],"id":{"eki":["509006531"],"zdb":["2225896-6"]},"origin":[{"publisherPlace":"Ithaca, NY ; [Erscheinungsort nicht ermittelbar]","dateIssuedDisp":"1991-","dateIssuedKey":"1991","publisher":"Cornell University ; Arxiv.org"}]}],"physDesc":[{"extent":"56 S."}]} 
SRT |a JOOSFELIXKOPTIMALPAC1320 

Similar Items