Girth and euclidean distortion

(MATH) In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in \cite{llr}. Let $G$ be a $k$-regular graph, $k \ge 3$, with girth $g$. We show that every embedding $f : G \to \ell_2$ has distortion $\Omega (\sqrt{g})$. The original conjecture which remains open is that the Euclidean distortion is bounded below by $\Omega(g)$. Two proofs are given, one based on semi-definite programming, and the other on Markov Type, a concept that considers random walks on metrics.

Authors

• Nati Linial
• Avner Magen
• Assaf Naor

Keywords

No keywords are indexed for this paper.