Optimal packings of bounded degree trees

Research output: Contribution to journalArticle

Standard

Harvard

APA

Vancouver

Author

Bibtex

@article{393e6c4fb0974ff3a3c0fa849f638a75,
title = "Optimal packings of bounded degree trees",
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{\'a}rf{\'a}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{\'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.",
keywords = "Graph decompositions, Packings, Quasirandomness, Trees",
author = "Felix Joos and Jaehoon Kim and Daniela Kuhn and Deryk Osthus",
year = "2019",
month = aug
day = "5",
doi = "10.4171/JEMS/909",
language = "English",
volume = "21",
journal = "Journal of the European Mathematical Society",
issn = "1435-9855",
publisher = "European Mathematical Society",
number = "12",

}

RIS

TY - JOUR

T1 - Optimal packings of bounded degree trees

AU - Joos, Felix

AU - Kim, Jaehoon

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2019/8/5

Y1 - 2019/8/5

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

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

KW - Graph decompositions

KW - Packings

KW - Quasirandomness

KW - Trees

UR - https://www.ems-ph.org/journals/forthcoming.php?jrn=jems

UR - http://www.scopus.com/inward/record.url?scp=85077328023&partnerID=8YFLogxK

U2 - 10.4171/JEMS/909

DO - 10.4171/JEMS/909

M3 - Article

VL - 21

JO - Journal of the European Mathematical Society

JF - Journal of the European Mathematical Society

SN - 1435-9855

IS - 12

ER -