On the ${\ell }^2$ distortion of random triangulations

Abstract

For each $n\in \mathbf{N}$, let $T_n$ be a uniformly random (rooted, Type I) triangulation of the sphere with $n$ vertices, viewed as a metric space equipped with its graph distance. We show that for every $\delta >0$, with probability tending to $1$ as $n\to \infty$, every embedding of $T_n$ into a separable Hilbert space has distortion at least $(\log n{)}^{1/4-\delta }$.

arXiv comment52 pages, 6 figures