Girth and Euclidean distortion

Nathan Linial, Avner Magen, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in [11]. Let G be a k-regular graph, k ≥ 3, with girth g. We show that every embedding f : G → ℓ2 has distortion Ω(√g). The original conjecture which remains open is that the Euclidean distortion is bounded below by Ω(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.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the Annual ACM Symposium on Theory of Computing
Number of pages7
StatePublished - 2002
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002


OtherProceedings of the 34th Annual ACM Symposium on Theory of Computing
CityMontreal, Que.

ASJC Scopus subject areas

  • Software


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

Cite this