JournalsjemsVol. 21, No. 12pp. 3573–3647

Optimal packings of bounded degree trees

  • Felix Joos

    University of Birmingham, UK
  • Jaehoon Kim

    Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea
  • Daniela Kühn

    University of Birmingham, UK
  • Deryk Osthus

    University of Birmingham, UK
Optimal packings of bounded degree trees cover
Download PDF

A subscription is required to access this article.

Abstract

We prove that if T1,,TnT_1,\dots, T_n is a sequence of bounded degree trees such that TiT_i has ii vertices, then KnK_n has a decomposition into T1,,TnT_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)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.

Cite this article

Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus, Optimal packings of bounded degree trees. J. Eur. Math. Soc. 21 (2019), no. 12, pp. 3573–3647

DOI 10.4171/JEMS/909