Stronger Lower Bounds for Tree Covers via Cyclic Symmetry
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$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.27264
curl -X POST /api/v1/records/arxiv/2607.27264/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.27264/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'