Buchumschlag

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...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Hauptverfasser: Joos, Felix (VerfasserIn) , Kim, Jaehoon (VerfasserIn) , Kühn, Daniela (VerfasserIn) , Osthus, Deryk (VerfasserIn)
Dokumenttyp: Article (Journal) Kapitel/Artikel
Sprache:Englisch
Veröffentlicht: 13 Jun 2016
In: Arxiv
Year: 2016, Pages: 1-56
DOI:10.48550/arXiv.1606.03953
Online-Zugang:Verlag, lizenzpflichtig, Volltext: https://doi.org/10.48550/arXiv.1606.03953
Verlag, lizenzpflichtig, Volltext: http://arxiv.org/abs/1606.03953
Volltext
Verfasserangaben: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  |d 910000  |d 950000  |d 950950  |e 910000PJ1075006171  |e 950000PJ1075006171  |e 950950PJ1075006171  |k 0/910000/  |k 1/910000/950000/  |k 2/910000/950000/950950/  |p 1  |x j 
999 |a KXP-PPN1810692040  |e 4169389794 
BIB |a Y 
JSO |a {"note":["Identifizierung der Ressource nach: 13 Mar 2019","Gesehen am 27.07.2022"],"name":{"displayForm":["Felix Joos, Jaehoon Kim, Daniela Kühn, and Deryk Osthus"]},"recId":"1810692040","person":[{"display":"Joos, Felix","role":"aut","family":"Joos","given":"Felix"},{"given":"Jaehoon","family":"Kim","role":"aut","display":"Kim, Jaehoon"},{"family":"Kühn","role":"aut","given":"Daniela","display":"Kühn, Daniela"},{"display":"Osthus, Deryk","family":"Osthus","role":"aut","given":"Deryk"}],"language":["eng"],"id":{"doi":["10.48550/arXiv.1606.03953"],"eki":["1810692040"]},"title":[{"title":"Optimal packings of bounded degree trees","title_sort":"Optimal packings of bounded degree trees"}],"origin":[{"dateIssuedKey":"2016","dateIssuedDisp":"13 Jun 2016"}],"physDesc":[{"extent":"56 S."}],"relHost":[{"recId":"509006531","language":["eng"],"disp":"Optimal packings of bounded degree treesArxiv","note":["Gesehen am 28.05.2024"],"pubHistory":["1991 -"],"physDesc":[{"extent":"Online-Ressource"}],"type":{"bibl":"edited-book","media":"Online-Ressource"},"part":{"extent":"56","pages":"1-56","text":"(2016), Artikel-ID 1606.03953, Seite 1-56","year":"2016"},"id":{"zdb":["2225896-6"],"eki":["509006531"]},"title":[{"title_sort":"Arxiv","title":"Arxiv"}],"origin":[{"dateIssuedDisp":"1991-","dateIssuedKey":"1991","publisher":"Cornell University ; Arxiv.org","publisherPlace":"Ithaca, NY ; [Erscheinungsort nicht ermittelbar]"}],"titleAlt":[{"title":"Arxiv.org"},{"title":"Arxiv.org e-print archive"},{"title":"Arxiv e-print archive"},{"title":"De.arxiv.org"}]}],"type":{"media":"Online-Ressource","bibl":"chapter"}} 
SRT |a JOOSFELIXKOPTIMALPAC1320 

Ähnliche Einträge