We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Proof of the tree packing conjecture for bounded degree trees

Formale Metadaten

Titel
Proof of the tree packing conjecture for bounded degree trees
Serientitel
Anzahl der Teile
24
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
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).
Schlagwörter