Hyperbolicity, slimness, and minsize, on average

Abstract

A metric space $(X,d)$ is said to be $\hat{I}´$-hyperbolic if $d(x,y)+d(z,w)$ is at most $\max (d(x,z)+d(y,w),d(x,w)+d(y,z))$ by $2\hat{I}´$. A geodesic space is $\hat{I}´$-slim if every geodesic triangle $\hat{I}”(x,y,z)$ is $\hat{I}´$-slim. It is well-established that the notions of $\hat{I}´$-slimness, $\hat{I}´$-hyperbolicity, $\hat{I}´$-thinness and similar concepts are equivalent up to a constant factor. In this paper, we investigate these properties under an average-case framework and reveal a surprising discrepancy: while $\mathbb{E}\hat{I}´$-slimness implies $\mathbb{E}\hat{I}´$-hyperbolicity, the converse does not hold. Furthermore, similar asymmetries emerge for other definitions when comparing average-case and worst-case formulations of hyperbolicity. We exploit these differences to analyze the random Gaussian distribution in Euclidean space, random $d$-regular graph, and the random Erdős-Rényi graph model, illustrating the implications of these average-case deviations.

28 pages, 7 figures