Girth and euclidean distortion

N. Linial; A. Magen; A. Naor

doi:10.1007/s00039-002-8251-y

Girth and euclidean distortion

N. Linial, A. Magen, A. Naor

Research output: Contribution to journal › Article › peer-review

41 Scopus citations

Abstract

Let G be a k-regular graph, k ≥ 3, with girth g. We prove that every embedding f : G → l₂ 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 language	English (US)
Pages (from-to)	380-394
Number of pages	15
Journal	Geometric and Functional Analysis
Volume	12
Issue number	2
DOIs	https://doi.org/10.1007/s00039-002-8251-y
State	Published - 2002
Externally published	Yes

All Science Journal Classification (ASJC) codes

Analysis
Geometry and Topology

Access to Document

10.1007/s00039-002-8251-y

Cite this

@article{4436e004d3844709a5058b73ca487b03,

title = "Girth and euclidean distortion",

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{\'e}-type inequalities on graph metrics.",

author = "N. Linial and A. Magen and A. Naor",

note = "Funding Information: N.L. was supported in part by grants from the Israel Science Foundation and the Binational Science Foundation Israel-USA. A.N. was supported in part by the Binational Science Foundation Israel-USA and the Clore Foundation. This work is part of a Ph.D. thesis being prepared under the supervision of Professor Joram Lindenstrauss.",

year = "2002",

doi = "10.1007/s00039-002-8251-y",

language = "English (US)",

volume = "12",

pages = "380--394",

journal = "Geometric and Functional Analysis",

issn = "1016-443X",

publisher = "Birkhauser Verlag Basel",

number = "2",

}

TY - JOUR

T1 - Girth and euclidean distortion

AU - Linial, N.

AU - Magen, A.

AU - Naor, A.

N1 - Funding Information: N.L. was supported in part by grants from the Israel Science Foundation and the Binational Science Foundation Israel-USA. A.N. was supported in part by the Binational Science Foundation Israel-USA and the Clore Foundation. This work is part of a Ph.D. thesis being prepared under the supervision of Professor Joram Lindenstrauss.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036435272&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036435272&partnerID=8YFLogxK

U2 - 10.1007/s00039-002-8251-y

DO - 10.1007/s00039-002-8251-y

M3 - Article

AN - SCOPUS:0036435272

SN - 1016-443X

VL - 12

SP - 380

EP - 394

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

IS - 2

ER -

Girth and euclidean distortion

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this