MATH Seminar

Title: Packing the largest trees in the tree packing conjecture
Seminar: Combinatorics
Speaker: Richard Montgomery of Warwick University
Contact: Liana Yepremyan, liana.yepremyan@emory.edu
Date: 2023-11-08 at 4:00PM
Venue: MSC E406
Download Flyer
Abstract: 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.