L1 distortion lower bound for an expander graph
ID: l1-distortion-lower-bound-for-an-expander-graph
If a -regular graph on vertices has expansion , its distortion obeysThe Poincare inequality controls average image distance by edge lengths, while bounded-degree ball growth makes the average graph distance comparable to .
New to topics? Read the docs here!