An approximate version of the tree packing conjecture

DOI10.1007/S11856-015-1277-2MaRDI QIDQ273108zbMATH OpenOpenAlexWikidataFDO

Authors Julia Böttcher, Jan Hladký, Diana Piguet, Anusch Taraz

Publication date 21 April 2016

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.0697, http://eprints.lse.ac.uk/65240/1/Bottcher_An%20approximate%20version.pdf

zbMATH Keywords

nibble methodrandom tree embedding process

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that for any pair of constants $epsilon>0$ and $Delta$ and for $n$ sufficiently large, every family of trees of orders at most $n$, maximum degrees at most $Delta$, and with at most $$ edges in total packs into $K_{(1+epsilon)n}$. This implies asymptotic versions of the Tree Packing Conjecture of Gyarfas from 1976 and a tree packing conjecture of Ringel from 1963 for trees with bounded maximum degree. A novel random tree embedding process combined with the nibble method forms the core of the proof.

Recommendations

• On the tree packing conjecture
• An approximate version of the tree packing conjecture via random embeddings
• Generalizations of the tree packing conjecture
• A short proof of the tree-packing theorem
• Tree packing and approximating \(k\)-cuts
• Optimal packings of bounded degree trees
• The planar tree packing theorem
• The planar tree packing theorem
• On the tree packing problem
• On the minimal packing of a tree with fixed vertices

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 3765842 (Why is no real title available?)
• scientific article; zbMATH DE number 3604921 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A correlation inequality and a poisson limit theorem for nonoverlapping balanced subgraphs of a random graph
• A note on packing trees into complete bipartite graphs and on Fishburn's conjecture
• Balanced integer arrays: a matrix packing theorem
• Concentration for self-bounding functions and an inequality of Talagrand
• On a packing and covering problem
• On packing trees into complete bipartite graphs
• On the tree packing conjecture
• Packing Trees into the Complete Graph
• Packing graphs: The packing problem solved
• Packing minor closed families of graphs
• Packing tree factors in random and pseudo-random graphs
• Packing trees in complete graphs
• Packings of graphs and applications to computational complexity
• Quasi-random graphs
• Random walks on quasirandom graphs
• Some remarks on packing trees
• Subgraphs of graphs. I
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The triangle-free process

Cited in

(28)

• Optimal packings of bounded degree trees
• A proof of Ringel's conjecture
• Packing minor-closed families of graphs into complete graphs
• Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
• A blow-up lemma for approximate decompositions
• Problems close to my heart
• Packing large trees of consecutive orders
• Packing degenerate graphs greedily
• Decomposing almost complete graphs by random trees
• scientific article; zbMATH DE number 4132205 (Why is no real title available?)
• Maximum tree-packing in time O(n5/2)
• scientific article; zbMATH DE number 89770 (Why is no real title available?)
• A note on packing of three forests
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Exact packing measure on a Galton-Watson tree
• Packing trees of unbounded degrees in random graphs
• On the tree packing conjecture
• Packing degenerate graphs
• A Short proof of the blow-up lemma for approximate decompositions
• Embedding rainbow trees with applications to graph labelling and decomposition
• Perfectly packing graphs with bounded degeneracy and many leaves
• Graph and hypergraph packing
• Almost all trees are almost graceful
• Seven largest trees pack
• An approximate version of the tree packing conjecture via random embeddings
• On cyclic packing of a tree
• Tree decompositions of graphs without large bipartite holes
• Packing spanning graphs from separable families

This page was built for publication: An approximate version of the tree packing conjecture

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