BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Proof of the tree packing conjecture for bounded degree trees Kuhn, Daniela

Description

We prove that given any sequence of $n$ bounded degree trees so that the $j$th tree has $j$ vertices, the complete graph on $n$ vertices has a decomposition into these trees, if $n$ is large enough. This shows that the tree packing conjecture of Gyarfas and Lehel from 1976 holds for all bounded degree trees. An important ingredient is a new tool for constructing approximate decompositions of dense quasirandom graphs into bounded degree graphs (which can be viewed as an extension of the classical blow-up lemma of Komlos, Sarkozy and Szemeredi to the setting of approximate decompositions). (Joint work Felix Joos, Jaehoon Kim, Deryk Osthus and Mykhaylo Tyomkyn)

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International