Id: arxiv/2607.27264 Url: https://arxiv.org/abs/2607.27264 Tags: math.CO, cs.DS Score: 0 Title: Stronger Lower Bounds for Tree Covers via Cyclic Symmetry Domain: math.CO Source: arxiv Authors: Shengtang Huang Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-29 Page: https://delphi.science/r/arxiv/2607.27264 A tree cover of an $n$-point metric space is a collection of $k$ dominating trees such that every pairwise distance is approximately preserved by at least one tree. The best known general upper bound on the distortion is $\widetilde{O}(n^{1/k})$. Recently, Chen, Tan, and Xu (ITCS 2026, SICOMP 2026) proved a lower bound of $Ω_k(n^{1/2^{k-1}})$ using a topological approach. We improve their lower bound to $Ω_k(n^{1/[k(p-1)]})=Ω_k(n^{1/O(k^2)})$, where $p$ is the smallest prime strictly larger than $k$. Thus, the gap between the known upper and lower exponents is reduced from exponential in $k$…