BIMSA >
Research seminar in Discrete Mathematics
Research seminar in Discrete Mathematics
Three trees suffice for a constant stretch in minor-free graphs
Three trees suffice for a constant stretch in minor-free graphs
Speaker
Tuan Tran
Time
Tuesday, September 29, 2026 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
Let (X, δ) be a metric space. A tree cover is a family F of edge-weighted trees, each dominating (X, δ), meaning d_T(u, v) is at least δ(u, v) for every tree T in F and all u, v. The cover has stretch t if every pair u, v has some tree T in F with d_T(u, v) at most t times δ(u, v). Tree covers let us reduce problems on complex metrics or graphs to problems on trees, which are usually easy to solve.
We show that H-minor-free graphs admit a tree cover with 3 trees and constant stretch, for any fixed H. This matches a lower bound of Chen, Tan, and Xu, who showed toroidal grids need at least 3 trees for constant stretch.
Joint work with Hung Le, Huy Pham, and Cuong Than.
We show that H-minor-free graphs admit a tree cover with 3 trees and constant stretch, for any fixed H. This matches a lower bound of Chen, Tan, and Xu, who showed toroidal grids need at least 3 trees for constant stretch.
Joint work with Hung Le, Huy Pham, and Cuong Than.
Speaker Intro
Tuan Tran is a professor at the University of Science and Technology of China (USTC). He earned his Ph.D. from the Free University of Berlin in 2015 under the supervision of Tibor Szabó. His research focuses on extremal and probabilistic combinatorics.