Journal of the European Mathematical Society

List online-first JEMS articles | JEMS summary
Published online first: 2019-08-05
DOI: 10.4171/JEMS/909

Optimal packings of bounded degree trees

Felix Joos[1], Jaehoon Kim[2], Daniela Kühn[3] and Deryk Osthus[4]

(1) University of Birmingham, UK
(2) Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea
(3) University of Birmingham, UK
(4) University of Birmingham, UK

We prove that if $T_1,\dots, 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,\dots, T_n$. 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.

Keywords: Trees, graph decompositions, packings, quasirandomness

Joos Felix, Kim Jaehoon, Kühn Daniela, Osthus Deryk: Optimal packings of bounded degree trees. J. Eur. Math. Soc. Electronically published on August 5, 2019. doi: 10.4171/JEMS/909 (to appear in print)