${\ell }^p$-distortion and $p$-spectral gap of finite regular graphs

Abstract

We give a lower bound for the ${\ell }^p$-distortion $c_p(X)$ of finite graphs $X$, depending on the first eigenvalue ${\lambda }_1^{(p)}(X)$ of the $p$-Laplacian and the maximal displacement of permutations of vertices. For a $k$-regular vertex-transitive graph it takes the form $c_p(X{)}^p\ge diam(X{)}^p{\lambda }_1^{(p)}(X)/2^{p-1}k$. This bound is optimal for expander families and, for $p=2$, it gives the exact value for cycles and hypercubes. As a new application we give a non-trivial lower bound for the ${\ell }^2$-distortion of a family of Cayley graphs of $S{L}_n(q)$ ($q$ fixed, $n\ge 2$) with respect to a standard two-element generating set.