(MATH) In this paper we partially prove a conjecture that was raised by Linial, London and Rabinovich in {llr}. 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.
No takes yet. Share an insight, caveat, or question.
Linial et al. (2002) studied this question.