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, \delta)$ be a metric space. A tree cover is a family $F$ of edge-weighted trees, each dominating $(X, \delta)$, meaning $d_T(u, v)$ is at least $\delta(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 $\delta(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 an Associate Professor of Mathematics at University of Science and Technology of China. He received his PhD from Free University of Berlin, under the supervision of Tibor Szabo. Before joining USTC, he held postdoctoral positions at Institute for Basic Science (Korea), ETH Zurich, and Czech Academy of Sciences.His main research interests are Extremal, Probabilistic and Additive Combinatorics.