A quantitative tree-likeness bound from average hyperbolicity

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 useful quantitative bounds. Here, we establish an explicit relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to [0,b]$, we prove that $$\text{Tree}(s)\le (63\mathrm{/}e{)}^{1\mathrm{/}3}\sqrt[3]{b^2\text{Hyp}(s)}\le 2.8512\sqrt[3]{b^2\text{Hyp}(s)}\mathrm{.}$$ The proof uses a simple pivoting construction inspired by $\text{textsc}KwikCluster$. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.