### Abstract

Let A = (aij) ∈ M_{n}(R) be an n by n symmetric stochastic matrix. For p ∈ [1,∞) and a metric space (X, d_{x}), let (A, d^{p} _{n}) be the inmum over those ∈ (0,1] for which every x_{1n}, . . . , x_{n} ∈ X satisfy 1 n^{2} Σn i=1 Σn j=1 dX(xi , xj)^{p} ≤ n Σn i=1 Σn j=1 aijdX(xi , xj)^{p} . Thus (A, dp X) measures the magnitude of the nonlinear spectral gap of the matrix A with respect to the kernel dp X : X × X ! [0,1). We study pairs of metric spaces (X, dX) and (Y, dY ) for which there exists : (0,1) ! (0,1) such that (A, dp X) 6 γ (A, dp Y ) for every symmetric stochastic A 2 M_{n}(R) with (A, dp Y ) < 1. When 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 2 N and p 2 (2,1) then for every f1, . . . , fn 2 Lp there exist x1, . . . , xn 2 L2 such that 8 i, j 2 f1, . . . , ng, kxi - xjk2 . pkfi - fjkp , (0.1) and Σn i=1 Σn j=1 kxi - xjk2 2 = Xn i=1 Xn j=1 kfi - fjk2 p . This statement is impossible for p ∈ [1, 2), and the asymptotic dependence on p in (0.1) is sharp. We also obtain the best known lower bound on the Lp distortion of Ramanujan graphs, improving over the work of Matoušek. Links to Bourgain-Milman-Wolfson type and a conjectural nonlinear Maurey-Pisier theorem are studied.

Original language | English (US) |
---|---|

Pages (from-to) | 1-52 |

Number of pages | 52 |

Journal | Analysis and Geometry in Metric Spaces |

Volume | 2 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2014 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Analysis
- Geometry and Topology
- Applied Mathematics

### Keywords

- Expanders
- Metric embeddings
- Nonlinear spectral gaps
- Nonlinear type