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

Mathematics – Metric Geometry

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

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 $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 $SL_n(q)$ ($q$ fixed, $n\geq 2$) with respect to a standard two-element generating set.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

$\ell^p$-distortion and $p$-spectral gap of finite regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with $\ell^p$-distortion and $p$-spectral gap of finite regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $\ell^p$-distortion and $p$-spectral gap of finite regular graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-324700

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.