Abstract.
Let G be a k-regular graph, \( k \ge 3 \), with girth g. We prove that every embedding \( f : G \to \ell_2 \) has distortion \( \Omega(\sqrt{g}) \). Two proofs are given, one based on Markov type [B] and the other on quadratic programming. In the core of both proofs are some Poincaré-type inequalities on graph metrics.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Submitted: July 2001, Revised: September 2001.
Rights and permissions
About this article
Cite this article
Linial, N., Magen, A. & Naor, A. Girth and Euclidean distortion . GAFA, Geom. funct. anal. 12, 380–394 (2002). https://doi.org/10.1007/s00039-002-8251-y
Issue Date:
DOI: https://doi.org/10.1007/s00039-002-8251-y