arXiv preprint ·
A quantitative tree-likeness bound from average hyperbolicity
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $$\operatorname{Tree}(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \operatorname{Hyp}(s)} \leq 2.8512 \sqrt[3]{b^2 \operatorname{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Probability
Continuous Optimization for p-adic Models
Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time $2^{0.292n}$
Dual lattice attacks for bounded distance decoding, revisited
The twisted convolution identity and ghost $r$-SICs from finite quantum dilogarithms
Quantum codes in the Lee metric
Get the few papers worth your time in Probability every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.