Girth and Euclidean Distortion

Avner Magen, NEC Research Institute, Princeton

March 12, 4:30 PM, Rutgers Univ. CORE 431

Abstract.

We partially prove a conjecture that was raised by Linial, London and Rabinovich in 1994. Let G be a k-regular graph, k > 2, with girth g. We show that every embedding of G to the Euclidean space has distortion Omega(g^.5). The original conjecture which remains open is that the Euclidean distortion is bounded below by Omega(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.

Joint work with Nati Linial and Assaf Naor.



Back to Discrete Math/Theory of Computing seminar