Girth and Euclidean distortion

Nathan Linial; Avner Magen; Assaf Naor

Girth and Euclidean distortion

Nathan Linial, Avner Magen, Assaf Naor

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 → ℓ₂ 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 language	English (US)
Title of host publication	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
Pages	705-711
Number of pages	7
State	Published - 2002
Event	Proceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada Duration: May 19 2002 → May 21 2002

Other

Other	Proceedings of the 34th Annual ACM Symposium on Theory of Computing
Country/Territory	Canada
City	Montreal, Que.
Period	5/19/02 → 5/21/02

ASJC Scopus subject areas

Software

Cite this

@inproceedings{34cda34df58b47f683a0eb15d33f4dfc,

title = "Girth and Euclidean distortion",

abstract = "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.",

author = "Nathan Linial and Avner Magen and Assaf Naor",

year = "2002",

language = "English (US)",

pages = "705--711",

booktitle = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

note = "Proceedings of the 34th Annual ACM Symposium on Theory of Computing ; Conference date: 19-05-2002 Through 21-05-2002",

}

TY - GEN

T1 - Girth and Euclidean distortion

AU - Linial, Nathan

AU - Magen, Avner

AU - Naor, Assaf

PY - 2002

Y1 - 2002

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0036038484

SP - 705

EP - 711

BT - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 34th Annual ACM Symposium on Theory of Computing

Y2 - 19 May 2002 through 21 May 2002

ER -

Girth and Euclidean distortion

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this