Comparison of metric spectral gaps

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² Σ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.