DC Field | Value | Language |
---|---|---|
dc.contributor.author | Joos, Felix | ko |
dc.contributor.author | Kim, Jaehoon | ko |
dc.contributor.author | Kuhn, Daniela | ko |
dc.contributor.author | Osthus, Deryk | ko |
dc.date.accessioned | 2019-11-01T01:20:15Z | - |
dc.date.available | 2019-11-01T01:20:15Z | - |
dc.date.created | 2019-10-31 | - |
dc.date.created | 2019-10-31 | - |
dc.date.created | 2019-10-31 | - |
dc.date.created | 2019-10-31 | - |
dc.date.created | 2019-10-31 | - |
dc.date.created | 2019-10-31 | - |
dc.date.created | 2019-10-31 | - |
dc.date.issued | 2019-10 | - |
dc.identifier.citation | JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, v.21, no.12, pp.3573 - 3647 | - |
dc.identifier.issn | 1435-9855 | - |
dc.identifier.uri | http://hdl.handle.net/10203/268113 | - |
dc.description.abstract | We prove that if T-1, ..., T-n is a sequence of bounded degree trees such that T-i has i vertices, then K-n has a decomposition into T-1, ..., 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 Szemeredi'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. | - |
dc.language | English | - |
dc.publisher | EUROPEAN MATHEMATICAL SOC | - |
dc.title | Optimal packings of bounded degree trees | - |
dc.type | Article | - |
dc.identifier.wosid | 000490547500001 | - |
dc.identifier.scopusid | 2-s2.0-85077328023 | - |
dc.type.rims | ART | - |
dc.citation.volume | 21 | - |
dc.citation.issue | 12 | - |
dc.citation.beginningpage | 3573 | - |
dc.citation.endingpage | 3647 | - |
dc.citation.publicationname | JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY | - |
dc.identifier.doi | 10.4171/JEMS/909 | - |
dc.contributor.localauthor | Kim, Jaehoon | - |
dc.contributor.nonIdAuthor | Joos, Felix | - |
dc.contributor.nonIdAuthor | Kuhn, Daniela | - |
dc.contributor.nonIdAuthor | Osthus, Deryk | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Trees | - |
dc.subject.keywordAuthor | graph decompositions | - |
dc.subject.keywordAuthor | packings | - |
dc.subject.keywordAuthor | quasirandomness | - |
dc.subject.keywordPlus | HAMILTON DECOMPOSITIONS | - |
dc.subject.keywordPlus | REGULAR EXPANDERS | - |
dc.subject.keywordPlus | GRAPHS | - |
dc.subject.keywordPlus | FAMILIES | - |
dc.subject.keywordPlus | PROOF | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.