A quantitative tree-likeness bound from average hyperbolicity

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\times S\to [0,b]$, we prove that $$\mathrm{Tree}(s)\le (63/e{)}^{1/3}\sqrt[3]{b^2\mathrm{Hyp}(s)}\le 2.8512\sqrt[3]{b^2\mathrm{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.

arXiv comment13 pages, 3 figures. Added comments on ultrametric fitting corollary, and AI statements