Three trees suffice for a constant stretch in minor-free graphs
演讲者
Tuan Tran
时间
2026年09月29日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
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.
演讲者介绍
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.