L^p-distortion and p-spectral gap of finite graphs

Abstract: We give a lower bound for the

e l l^{p}

-distortion

c_{p} (X)

of finite graphs

X

, depending on the first eigenvalue

l a m b d a_{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} g e q d i a m (X)^{p} l a m b d a_{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

e l l^{2}

-distortion of a family of Cayley graphs of

S L_{n} (q)

(

q

fixed,

n g e q 2

) with respect to a standard two-element generating set.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs