Comparison of metric spectral gaps

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Stochastic matrices (15B51) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Abstract: Let

A = (a_{i j}) i n M_{n} (R)

be an

n

by

n

symmetric stochastic matrix. For

p i n [1, i n f t y)

and a metric space

(X, d_{X})

, let

g a m m a (A, d_{X}^{p})

be the infimum over those

g a m m a i n (0, i n f t y]

for which every

x_{1}, ..., x_{n} i n X

satisfy

frac{1}{n^2} sum_{i=1}^nsum_{j=1}^n d_X(x_i,x_j)^ple frac{gamma}{n}sum_{i=1}^nsum_{j=1}^n a_{ij} d_X(x_i,x_j)^p.

Thus

g a m m a (A, d_{X}^{p})

measures the magnitude of the {em nonlinear spectral gap} of the matrix

A

with respect to the kernel

d_{X}^{p} : X i m e s X o [0, i n f t y)

. We study pairs of metric spaces

(X, d_{X})

and

(Y, d_{Y})

for which there exists

P s i : (0, i n f t y) o (0, i n f t y)

such that

g a m m a (A, d_{X}^{p}) l e P s i (g a m m a (A, d_{Y}^{p}))

for every symmetric stochastic

A i n M_{n} (R)

with

g a m m a (A, d_{Y}^{p}) < i n f t y

. When

P s i

is linear a complete geometric characterization is obtained. Our estimates on nonlinear spectral gaps yield new embeddability results as well as new nonembeddability results. For example, it is shown that if

n i n N

and

p i n (2, i n f t y)

then for every

f_{1}, ..., f_{n} i n L_{p}

there exist

x_{1}, ..., x_{n} i n L_{2}

such that {equation}label{eq:p factor} forall, i,jin {1,...,n},quad |x_i-x_j|_2lesssim p|f_i-f_j|_p, {equation} and

sum_{i=1}^nsum_{j=1}^n |x_i-x_j|_2^2=sum_{i=1}^nsum_{j=1}^n |f_i-f_j|_p^2.

This statement is impossible for

p i n [1, 2)

, and the asymptotic dependence on

p

in eqref{eq:p factor} is sharp. We also obtain the best known lower bound on the

L_{p}

distortion of Ramanujan graphs, improving over the work of Matouv{s}ek. Links to Bourgain--Milman--Wolfson type and a conjectural nonlinear Maurey--Pisier theorem are studied.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Comparison of metric spectral gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402099)