The tree packing conjecture for bounded degree trees

The tree packing conjecture for bounded degree trees

-
Jaehoon Kim, University of Birmingham
Fine Hall 224

We prove that, for sufficiently large n, if T_1 ... T_n is a sequence of bounded degree trees so 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árfás and Lehel from 1976 holds for all bounded degree trees. We deduce this result from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. In this talk, we discuss ideas used in the proof. This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.