Expanders with respect to random regular graphs

Expanders with respect to random regular graphs

-
Manor Mendel , Open U Israel and IAS
Fine Hall 224

The discrete Poincare inequality (PI) for a regular graph G=(V,E) is the following: For any mapping f:V-->H of the vertices into Hilbert space, the average of ||f(u)-f(v)||^2 over all pairs of vertices is at most the average of ||f(u)-f(v)||^2 over the edges (E) times 1/(1-lambda_2(G)), where lambda_2(G) is the second normalized eigenvalue of G. This inequality has a natural metric interpretation: There is no way to embed a constant degree expander in Hilbert space while "uniformly" preserving the shortest path metric, since in the shortest path metric the average square distance over all pairs is unbounded, whereas the average over the edges is (at most) 1. Motivated by this application, PI has been strengthen by replacing Hilbert space with other metric spaces X. However, until recently it was unknown whether all expanders are equivalent in this context, namely whether for any two expanders Z and W and a metric space X, Z satisfies PI w.r.t. X if and only if W satisfies PI w.r.t. X. In this talk I will show that the answer is negative by exhibiting an expander that a.a.s. satisfies the discrete Poincare inequality with respect to the shortest path metric of random constant degree graph. The proof uses the zigzag expander construction (Reingold et. al.), non-positively curved Euclidean cones over high-girth graphs (Berestovskii; Gromov; Kondo), Markov cotype (Ball), and embedding of small subsets of random graphs in L_1 (Arora et. al.). Joint work with Assaf Naor.