Comparison of metric spectral gaps

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

Let A = (aij) ∈ Mn(R) be an n by n symmetric stochastic matrix. For p ∈ [1,∞) and a metric space (X, dx), let (A, dp n) be the inmum over those ∈ (0,1] for which every x1n, . . . , xn ∈ X satisfy 1 n2 Σ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 Mn(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 languageEnglish (US)
Pages (from-to)1-52
Number of pages52
JournalAnalysis and Geometry in Metric Spaces
Volume2
Issue number1
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Geometry and Topology
  • Applied Mathematics

Keywords

  • Expanders
  • Metric embeddings
  • Nonlinear spectral gaps
  • Nonlinear type

Fingerprint Dive into the research topics of 'Comparison of metric spectral gaps'. Together they form a unique fingerprint.

  • Cite this