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.
ASJC Scopus subject areas
- Geometry and Topology