Document Open Access Logo

An Approximate Version of the Tree Packing Conjecture via Random Embeddings

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.490.pdf
  • Filesize: 476 kB
  • 10 pages

Document Identifiers

Author Details

Julia Böttcher
Jan Hladký
Diana Piguet
Anusch Taraz

Cite As Get BibTex

Julia Böttcher, Jan Hladký, Diana Piguet, and Anusch Taraz. An Approximate Version of the Tree Packing Conjecture via Random Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 490-499, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.490

Abstract

We prove that for any pair of constants a>0 and D and for n sufficiently large, every family of trees of orders at most n, maximum degrees at most D, and with at most n(n-1)/2 edges in total packs into the complete graph of order (1+a)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.

Subject Classification

Keywords
  • tree packing conjecture
  • Ringel’s conjecture
  • random walks
  • quasirandom graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon and J. H. Spencer. The probabilistic method. Wiley, Hoboken, NJ, third edition, 2008. Google Scholar
  2. J. Balogh and C. Palmer. On the Tree Packing Conjecture. SIAM J. Discrete Math., 27(4):1995-2006, 2013. Google Scholar
  3. B. Barber and E. Long. Random walks on quasirandom graphs. Electron. J. Combin., 20(4):Paper 25, 2013. Google Scholar
  4. B. Bollobás. Some remarks on packing trees. Discrete Math., 46(2):203-204, 1983. Google Scholar
  5. J. Böttcher, J. Hladký, D. Piguet, and A. Taraz. An approximate version of the tree packing conjecture. arXiv:1404.0697. Google Scholar
  6. Y. Caro and Y. Roditty. A note on packing trees into complete bipartite graphs and on Fishburn’s conjecture. Discrete Math., 82(3):323-326, 1990. Google Scholar
  7. Y. Caro and R. Yuster. Packing graphs: the packing problem solved. Electron. J. Combin., 4(1):Paper 1, 1997. Google Scholar
  8. F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs. Combinatorica, 9(4):345-362, 1989. Google Scholar
  9. O. Cooley. Proof of the Loebl-Komlós-Sós conjecture for large, dense graphs. Discrete Math., 309(21):6190-6228, 2009. Google Scholar
  10. E. Dobson. Packing trees into the complete graph. Combin. Probab. Comput., 11(3):263-272, 2002. Google Scholar
  11. P. C. Fishburn. Balanced integer arrays: a matrix packing theorem. J. Combin. Theory Ser. A, 34(1):98-101, 1983. Google Scholar
  12. A. Gyárfás and J. Lehel. Packing trees of different order into K_n. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), volume 18 of Colloq. Math. Soc. János Bolyai, pages 463-469. North-Holland, Amsterdam, 1978. Google Scholar
  13. J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein, and E. Szemerédi. The approximate Loebl-Komlós-Sós conjecture. arXiv:1211.3050. Google Scholar
  14. J. Hladký and D. Piguet. Loebl-Komlós-Sós Conjecture: dense case. arXiv:0805:4834. Google Scholar
  15. A. M. Hobbs. Packing trees. In Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. II (Baton Rouge, La., 1981), volume 33, pages 63-73, 1981. Google Scholar
  16. A. M. Hobbs, B. A. Bourgeois, and J. Kasiraj. Packing trees in complete graphs. Discrete Math., 67(1):27-42, 1987. Google Scholar
  17. C. McDiarmid. On the method of bounded differences. In Surveys in combinatorics, 1989 (Norwich, 1989), volume 141 of London Math. Soc. Lecture Note Ser., pages 148-188. Cambridge Univ. Press, Cambridge, 1989. Google Scholar
  18. G. Ringel. Problem 25. In Theory of Graphs and its Applications (Proc. Int. Symp. Smolenice 1963). Czech. Acad. Sci., Prague, 1963. Google Scholar
  19. V. Rödl. On a packing and covering problem. European J. Combin., 6(1):69-78, 1985. Google Scholar
  20. W.-C. S. Suen. A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph. Random Structures Algorithms, 1(2):231-242, 1990. Google Scholar
  21. A. Thomason. Pseudorandom graphs. In Random graphs '85 (Poznań, 1985), volume 144 of North-Holland Math. Stud., pages 307-331. North-Holland, Amsterdam, 1987. Google Scholar
  22. R. Yuster. On packing trees into complete bipartite graphs. Discrete Math., 163(1-3):325-327, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact