Packing the largest trees in the tree packing conjecture
- Series
- Graph Theory Seminar
- Time
- Tuesday, November 7, 2023 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Richard Montgomery – University of Warwick – richard.montgomery@warwick.ac.uk
The well-known tree packing conjecture of Gyárfás from 1976 says that, given any sequence of n trees in which the ith tree has i vertices, the trees can be packed edge-disjointly into the complete n-vertex graph. Packing even just the largest trees in such a sequence has proven difficult, with Bollobás drawing attention to this in 1995 by conjecturing that, for each k, if n is sufficiently large then the largest k trees in any such sequence can be packed. This has only been shown for k at most 5, by Zak, despite many partial results and much related work on the full tree packing conjecture.
I will discuss a result which proves Bollobás's conjecture by showing that, moreover, a linear number of the largest trees can be packed in the tree packing conjecture. This is joint work with Barnabás Janzer.