A quantitative tree-likeness bound from average hyperbolicity

Source 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 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 \[ \Tree(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \Hyp(s)} \leq 2.8512 \sqrt[3]{b^2 \Hyp(s)}.\] The proof uses a simple pivoting construction inspired by \textsc{KwikCluster}. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.