<i>L</i> <sup> <i>p</i> </sup> -distortion and <i>p</i> -spectral gap of finite graphs
<i>L</i> <sup> <i>p</i> </sup> -distortion and <i>p</i> -spectral gap of finite graphs
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}\geq diam(X)^{p}\lambda_{1}^{(p)}(X)/2^{p-1}k$. This bound is optimal for expander families and, for …