Nonlinear spectral calculus and super-expanders

2012/07/31 by Manor Mendel, Assaf Naor · 1 citation
Mathematics · #Advanced Banach Space Theory #Advanced Operator Algebra Research #Advanced Topics in Algebra #Calculus (dental) #Computer science #Embedding #Geometry #Mathematical analysis #Mathematics #Nonlinear system #Normed vector space #Physics #Pure mathematics #Regular polygon #Sequence (biology) #Space (punctuation) #Spectral gap #Zigzag #math.CO #math.FA #math.MG

paper · pdf · doi:10.1007/s10240-013-0053-2

published as Publications mathématiques de l'IHÉS 119(1), 1-95, 2014 · Typos fixed based on referee comments. Some of the results of this paper were announced in arXiv:0910.2041. The corresponding parts of arXiv:0910.2041 are subsumed by the current paper

arxiv created 2013/03/20 · openalex publication_date 2013/11/08 · arxiv updated 2014/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Nonlinear spectral gaps with respect to uniformly convex normed spaces are shown to satisfy a spectral calculus inequality that establishes their decay along Cesàro averages. Nonlinear spectral gaps of graphs are also shown to behave sub-multiplicatively under zigzag products. These results yield a combinatorial construction of super-expanders, i.e., a sequence of 3-regular graphs that does not admit a coarse embedding into any uniformly convex normed space.

Citations

• Towards a Calculus for Non-Linear Spectral Gaps [Extended Abstract]
• Filling Riemannian manifolds
• Euclidean quotients of finite metric spaces
• Expander graphs and their applications
• Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs
• Martingales with values in uniformly convex spaces
• On lipschitz embedding of finite metric spaces in Hilbert space
• Inequalities in Fourier Analysis
• L₁ embeddings of the Heisenberg group and fast estimation of graph isoperimetry
• Metric Spaces of Non-Positive Curvature
• Diameters and eigenvalues
• The geometry of graphs and some of its algorithmic applications
• Proceedings of the International Congress of Mathematicians

Cited by

• A universal threshold for geometric embeddings of trees