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 obeys
The 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!