Optimal packings of bounded degree trees

DOI10.4171/JEMS/909zbMATH Open1429.05164arXiv1606.03953OpenAlexW2964207094MaRDI QIDQ2279501FDOQ2279501

Authors: Felix Joos, Jaehoon Kim, Deryk Osthus, Daniela Kühn 

Publication date: 12 December 2019

Published in: Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Abstract: We prove that if $T_1,dots,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,dots,T_n$. This shows that the tree packing conjecture of Gy'arf'as 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'{e}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.

Full work available at URL: https://arxiv.org/abs/1606.03953

Recommendations

• Perfectly packing graphs with bounded degeneracy and many leaves
• A blow-up lemma for approximate decompositions
• Packing trees of bounded diameter into the complete graph
• Decompositions of graphs into trees
• An approximate version of the tree packing conjecture

zbMATH Keywords

treespackingsgraph decompositionsquasirandomness

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• A dynamic survey of graph labeling
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Packing trees in complete graphs
• Blow-up lemma
• Balanced integer arrays: a matrix packing theorem
• Some remarks on packing trees
• Weighted sums of certain dependent random variables
• An approximate version of the tree packing conjecture
• Packing minor-closed families of graphs into complete graphs
• Packing Trees into the Complete Graph
• Packing tree factors in random and pseudo-random graphs
• Title not available (Why is that?)
• On the tree packing conjecture
• Probability theory. A comprehensive course
• Concentration of the hypergeometric distribution
• New families of graphs that have \(\alpha\)-labelings
• Packing spanning graphs from separable families
• Hamiltonian degree sequences in digraphs
• An existence theory for pairwise balanced designs. II: Structure of PBD- closed sets and the existence conjectures
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Edge-disjoint Hamilton cycles in random graphs
• An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
• An existence theory for pairwise balanced designs. I: Composition theorems and morphisms
• Packing and decomposition of graphs with trees
• Packing trees of unbounded degrees in random graphs
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• A blow-up lemma for approximate decompositions
• On the decomposition threshold of a given graph
• A bandwidth theorem for approximate decompositions
• Packing large trees of consecutive orders
• Almost all trees are almost graceful
• Title not available (Why is that?)
• Almost every tree with \(m\) edges decomposes \(K_{2m,2m}\)
• Decomposing almost complete graphs by random trees

Cited In (34)

• Packing trees of unbounded degrees in random graphs
• Recent developments on gracefulness of graphs. A survey complemented with chessboard representations
• Packing a number of copies of a \(( p , q )\)-graph
• Counting oriented trees in digraphs with large minimum semidegree
• A bandwidth theorem for approximate decompositions
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• An approximate version of the tree packing conjecture
• Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
• Exact packing measure on a Galton-Watson tree
• Tree decompositions of graphs without large bipartite holes
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Seven largest trees pack
• A blow-up lemma for approximate decompositions
• Perfectly packing graphs with bounded degeneracy and many leaves
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
• Decompositions of graphs into trees
• An approximate version of the tree packing conjecture via random embeddings
• Embedding rainbow trees with applications to graph labelling and decomposition
• Graph and hypergraph packing
• Pseudorandom hypergraph matchings
• Packing degenerate graphs
• Almost all trees are almost graceful
• Resolution of the Oberwolfach problem
• Minimalist designs
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Resolution of the Oberwolfach problem
• A rainbow blow-up lemma
• Maximum tree-packing in time O(n5/2)
• A Short proof of the blow-up lemma for approximate decompositions
• Packing degenerate graphs greedily
• A proof of Ringel's conjecture
• Finding large rainbow trees in colourings of \(K_{n, n}\)

This page was built for publication: Optimal packings of bounded degree trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279501)