Girth and euclidean distortion

N. Linial, A. Magen, A. Naor

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


Let G be a k-regular graph, k ≥ 3, with girth g. We prove that every embedding f : G → l2 has distortion Ω(√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.

Original languageEnglish (US)
Pages (from-to)380-394
Number of pages15
JournalGeometric and Functional Analysis
Issue number2
StatePublished - 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Geometry and Topology


Dive into the research topics of 'Girth and euclidean distortion'. Together they form a unique fingerprint.

Cite this