The Library
Optimal packings of bounded degree trees
Tools
Tools
Tools
Joos, Felix, Kim, Jaehoon, Kühn, Daniela and Osthus, Deryk (2019) Optimal packings of bounded degree trees. Journal of the European Mathematical Society, 21 (12). pp. 3573-3647. doi:10.4171/JEMS/909 ISSN 1435-9855.
|
PDF
WRAP-optimal-packings-bounded-degree-trees-Joos-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1737Kb) | Preview |
Official URL: https://doi.org/10.4171/JEMS/909
Abstract
We prove that if T1,…,Tn is a sequence of bounded degree trees such that Ti has i vertices, then Kn has a decomposition into T1,…,Tn. This shows that the tree packing conjecture of Gyárfás 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é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.
| Item Type: | Journal Article | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Computer science -- Mathematics, Computer algorithms | ||||||||||||||||||
| Journal or Publication Title: | Journal of the European Mathematical Society | ||||||||||||||||||
| Publisher: | European Mathematical Society Publishing House | ||||||||||||||||||
| ISSN: | 1435-9855 | ||||||||||||||||||
| Official Date: | 5 August 2019 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Volume: | 21 | ||||||||||||||||||
| Number: | 12 | ||||||||||||||||||
| Page Range: | pp. 3573-3647 | ||||||||||||||||||
| DOI: | 10.4171/JEMS/909 | ||||||||||||||||||
| Institution: | University of Warwick | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
| Date of first compliant deposit: | 20 June 2019 | ||||||||||||||||||
| Date of first compliant Open Access: | 21 June 2019 | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
