Optimal packings of bounded degree trees

DOI10.4171/JEMS/909MaRDI QIDQ2279501zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

graph decompositionspackingsquasirandomnesstrees

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)

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.

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

Cites work

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

Cited in

(37)

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

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)