Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 59 min ago
PreprintarXiv licencearXiv

A quantitative tree-likeness bound from average hyperbolicity

  • Joon-Hyeok Yim
Open at sourcePDFDOICite

Abstract

Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield explicit quantitative bounds. Here, we establish a tighter relation between average hyperbolicity and mean tree approximation error. For a similarity function s:S× S→[0,b], we prove that Tree(s) ≤ (63/e)1/3 √[3]b2 Hyp(s) ≤ 2.8512 √[3]b2 Hyp(s). The proof uses a simple pivoting construction inspired by \KwikCluster. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.

Related

  1. Average lower bound on magnetic double-well tunneling with asymptotically large well separation
    Charles L. Fefferman, Say-Yeon Kwon, Jacob Shapiro +1
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsMathematical physicsarXiv
  2. The diameter of recoloring graphs under a maximum average degree bound
    Ruilin Zheng, Junying Lu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Quantitative lower bound for Pythagorean pairs in boxes of prime powers
    Rongzhong Xiao
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. The Density and Quantitative Upper Bound of Integers Not Expressible as the Sum of a Prime and a Zumkeller Number
    Ting Hon Stanford Li
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  5. A quantitative replica-symmetric bound for Sherrington--Kirkpatrick model in the entire de Almeida--Thouless region
    Seiichiro Kusuoka, Shuta Nakajima
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{yim2026quantitative,
  title = {{A quantitative tree-likeness bound from average hyperbolicity}},
  author = {Joon-Hyeok Yim},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.18023},
  eprint = {2609.18023},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.18023},
}
RIS
TY  - UNPB
TI  - A quantitative tree-likeness bound from average hyperbolicity
AU  - Joon-Hyeok Yim
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.18023
UR  - https://arxiv.org/abs/2609.18023
AB  - Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield explicit quantitative bounds. Here, we establish a tighter relation between average hyperbolicity and mean tree approximation error. For a similarity function s:S× S→[0,b], we prove that Tree(s) ≤ (63/e)^1/3 √[3]b^2 Hyp(s) ≤ 2.8512 √[3]b^2 Hyp(s). The proof uses a simple pivoting construction inspired by \KwikCluster. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.
ER  -