Skip to content
DraconiticResearch
Search Sources API
197,783 studies31 sourcesUpdated 29 min ago
PreprintarXiv licencearXiv

Improved Lower Bounds on Tree Covers

  • Yu Chen
  • Shengtang Huang
  • Zihan Tan
  • Hangyu Xu
Open at sourcePDFDOICite

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 Õ(n1/k) and the best known lower bound is Ωk(n1/2k−1). In this paper, we prove a lower bound of Ωk(n1/(k−1)2) for all k≥ 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.

Related

  1. Improved bounds for universal convex covers of unit arcs
    Ethan Keller
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  2. Improved Explicit and Algorithmic Lower Bounds for r(5,t)
    Amrit Kandasamy, Lawrence Zhou, Levi Segal
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Stability for the adjoint Finner inequality and improved lower bounds on the k-plane transform
    Jonathan Bennett, Sewook Oh
    arXivPreprintCC BY-NC-ND 4.0Full textAnalysis & PDEsarXiv
  4. Improved Gradient Descent Lower Bounds Beyond Nesterov
    Yuhan Ye, Kaizhao Liu
    arXivPreprintCC BY 4.0Full textOptimisation & controlStatisticsarXiv
  5. Three Improved Lower Bounds for Binary Error-Correcting Codes
    Kazuki Ota, Takayuki Osa, Tatsuya Harada
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026improved,
  title = {{Improved Lower Bounds on Tree Covers}},
  author = {Yu Chen and Shengtang Huang and Zihan Tan and Hangyu Xu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2607.27264},
  eprint = {2607.27264},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.27264},
}
RIS
TY  - UNPB
TI  - Improved Lower Bounds on Tree Covers
AU  - Yu Chen
AU  - Shengtang Huang
AU  - Zihan Tan
AU  - Hangyu Xu
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2607.27264
UR  - https://arxiv.org/abs/2607.27264
AB  - 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 Õ(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≥ 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.
ER  -