Improved Lower Bounds on Tree Covers
Yu Chen, Shengtang Huang, Zihan Tan, Hangyu Xu
A tree cover of an $n$-point metric space is a collection of $k$ trees such that every pairwise distance is approximately preserved in at least one tree. For fixed $k$, the best known distortion upper bound is $\tilde{O}(n^{1/k})$ and the best known lower bound is $Ω_k(n^{1/2^{k-1}})$. In this paper, we prove a lower bound of $Ω_k(n^{1/(k-1)^2})$ for all $k\ge 3$, significantly narrowing the gap towards the upper bound. Our approach makes use of a novel algebraic topological notion that we call the \emph{agreement index}: the equivariant topological index of a simplicial complex encoding pairwise agreement among tree labels. This notion helps characterize the power and limit of algebraic and topological methods for analyzing tree covers, and we believe it will also find applications to other problems.
尚无 AI 解读，展示原文摘要