Paperlane

no. 4 · Wednesday 28 October 2026

Improved Lower Bounds on Tree Covers

Yu Chen, Shengtang Huang, Zihan Tan and Hangyu Xu

math.CO · v2

Abstract

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.

fields
Combinatorics
pdf ↗ page arXiv:2607.27264 ↗