Girth and euclidean distortion

N. Linial, A. Magen, A. Naor

Research output: Contribution to journalArticle

31 Scopus citations

Abstract

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
Volume12
Issue number2
DOIs
StatePublished - Jan 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Geometry and Topology

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

  • Cite this