In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in . 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 language||English (US)|
|Number of pages||7|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - Jan 1 2002|
|Event||Proceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada|
Duration: May 19 2002 → May 21 2002
All Science Journal Classification (ASJC) codes