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.
Accepted:
Online First:
Published online:
DOI: 10.1007/s10240-013-0053-2
Manor Mendel 1; Assaf Naor 2
@article{PMIHES_2014__119__1_0,
author = {Manor Mendel and Assaf Naor},
title = {Nonlinear spectral calculus and super-expanders},
journal = {Publications Math\'ematiques de l'IH\'ES},
pages = {1--95},
year = {2014},
publisher = {Springer Berlin Heidelberg},
address = {Berlin/Heidelberg},
volume = {119},
doi = {10.1007/s10240-013-0053-2},
zbl = {1306.46021},
language = {en},
url = {https://pmihes.centre-mersenne.org/articles/10.1007/s10240-013-0053-2/}
}
TY - JOUR AU - Manor Mendel AU - Assaf Naor TI - Nonlinear spectral calculus and super-expanders JO - Publications Mathématiques de l'IHÉS PY - 2014 SP - 1 EP - 95 VL - 119 PB - Springer Berlin Heidelberg PP - Berlin/Heidelberg UR - https://pmihes.centre-mersenne.org/articles/10.1007/s10240-013-0053-2/ DO - 10.1007/s10240-013-0053-2 LA - en ID - PMIHES_2014__119__1_0 ER -
%0 Journal Article %A Manor Mendel %A Assaf Naor %T Nonlinear spectral calculus and super-expanders %J Publications Mathématiques de l'IHÉS %D 2014 %P 1-95 %V 119 %I Springer Berlin Heidelberg %C Berlin/Heidelberg %U https://pmihes.centre-mersenne.org/articles/10.1007/s10240-013-0053-2/ %R 10.1007/s10240-013-0053-2 %G en %F PMIHES_2014__119__1_0
Manor Mendel; Assaf Naor. Nonlinear spectral calculus and super-expanders. Publications Mathématiques de l'IHÉS, Volume 119 (2014), pp. 1-95. doi: 10.1007/s10240-013-0053-2
[1.] An elementary construction of constant-degree expanders, Comb. Probab. Comput., Volume 17 (2008), pp. 319-327 | Zbl | DOI
[2.] The Probabilistic Method (2008) | Zbl
[3.] Property (T) and rigidity for actions on Banach spaces, Acta Math., Volume 198 (2007), pp. 57-105 | Zbl | DOI
[4.] Markov chains, Riesz transforms and Lipschitz maps, Geom. Funct. Anal., Volume 2 (1992), pp. 137-172 | Zbl | DOI
[5.] Sharp uniform convexity and smoothness inequalities for trace norms, Invent. Math., Volume 115 (1994), pp. 463-482 | Zbl | DOI
[6.] On metric Ramsey-type phenomena, Ann. Math., Volume 162 (2005), pp. 643-709 | Zbl | DOI
[7.] Inequalities in Fourier analysis, Ann. Math., Volume 102 (1975), pp. 159-182 | Zbl | DOI
[8.] Étude des coefficients de Fourier des fonctions de Lp(G), Ann. Inst. Fourier (Grenoble), Volume 20 (1971), pp. 335-402 | Zbl | Numdam | DOI
[9.] An inequality and a characterization of the normal distribution connected with it, Teor. Veroâtn. Ee Primen., Volume 28 (1983), pp. 209-218 | Zbl
[10.] On Lipschitz embedding of finite metric spaces in Hilbert space, Isr. J. Math., Volume 52 (1985), pp. 46-52 | Zbl | DOI
[11.] Metric Spaces of Non-positive Curvature (1999) | Zbl
[12.] Groups with the Haagerup Property (2001) | Zbl
[13.] Diameters and eigenvalues, J. Am. Math. Soc., Volume 2 (1989), pp. 187-195 | Zbl | DOI
[14.] On the moduli of convexity and smoothness, Stud. Math., Volume 56 (1976), pp. 121-155 | Zbl
[15.] Séries aléatoires dans les espaces uniformément convexes ou uniformément lisses, C. R. Acad. Sci. Paris Sér. A, Volume 279 (1974), pp. 611-614 | Zbl
[16.] Harmonic Measure (2008) | Zbl
[17.] Filling Riemannian manifolds, J. Differ. Geom., Volume 18 (1983), pp. 1-147 | Zbl
[18.] Asymptotic invariants of infinite groups, Geometric Group Theory, Vol. 2 (1993), pp. 1-295
[19.] Random walk in random groups, Geom. Funct. Anal., Volume 13 (2003), pp. 73-146 | Zbl | DOI
[20.] The Novikov conjecture for linear groups, Publ. Math. Inst. Hautes Études Sci., Volume 101 (2005), pp. 243-268 | Zbl | Numdam | DOI
[21.] Expander graphs and their applications, Bull., New Ser., Am. Math. Soc., Volume 43 (2006), pp. 439-561 | Zbl | DOI
[22.] A nonreflexive Banach space that is uniformly nonoctahedral, Isr. J. Math., Volume 18 (1974), pp. 145-155 | Zbl | DOI
[23.] Nonreflexive spaces of type 2, Isr. J. Math., Volume 30 (1978), pp. 1-13 | Zbl | DOI
[24.] The octahedral problem for Banach spaces, Proceedings of the Seminar on Random Series, Convex Sets and Geometry of Banach Spaces (Mat. Inst., Aarhus Univ., Aarhus, 1974; Dedicated to the Memory of E. Asplund) (1975), pp. 100-120 | Zbl
[25.] The uniform structure of Banach spaces, Math. Ann., Volume 354 (2012), pp. 1247-1288 | Zbl | DOI
[26.] An F-Space Sampler (1984) | Zbl
[27.] The coarse geometric Novikov conjecture and uniform convexity, Adv. Math., Volume 206 (2006), pp. 1-56 | Zbl | DOI
[28.] Nonembeddability theorems via Fourier analysis, Math. Ann., Volume 334 (2006), pp. 821-852 | Zbl | DOI
[29.] Un renforcement de la propriété (T), Duke Math. J., Volume 143 (2008), pp. 559-602 | Zbl | DOI
[30.] Propriété (T) renforcée Banachique et transformation de Fourier rapide, J. Topol. Anal., Volume 1 (2009), pp. 191-206 | Zbl | DOI
[31.] Propriété (T) renforcée et conjecture de Baum-Connes, Quanta of Maths (2010), pp. 323-345 | Zbl
[32.] The Concentration of Measure Phenomenon (2001) | Zbl
[33.] On the modulus of smoothness and divergent series in Banach spaces, Mich. Math. J., Volume 10 (1963), pp. 241-252 | Zbl | DOI
[34.] Classical Banach Spaces. II (1979) | Zbl
[35.] The geometry of graphs and some of its algorithmic applications, Combinatorica, Volume 15 (1995), pp. 215-245 | Zbl | DOI
[36.] Expander graphs in pure and applied mathematics, Bull., New Ser., Am. Math. Soc., Volume 49 (2012), pp. 113-162 | Zbl | DOI
[37.] Ramanujan graphs, Combinatorica, Volume 8 (1988), pp. 261-277 | Zbl | DOI
[38.] Lipschitz functions on spaces of homogeneous type, Adv. Math., Volume 33 (1979), pp. 257-270 | Zbl | DOI
[39.] The Theory of Error-Correcting Codes. I (1977) | Zbl
[40.] Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Probl. Pereda. Inf., Volume 24 (1988), pp. 51-60 | Zbl
[41.] On embedding expanders into ℓp spaces, Isr. J. Math., Volume 102 (1997), pp. 189-197 | Zbl | DOI
[42.] Type, cotype and K-convexity, Handbook of the Geometry of Banach Spaces (2003), pp. 1299-1332 | Zbl
[43.] Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach, Stud. Math., Volume 58 (1976), pp. 45-90 | Zbl
[44.] Euclidean quotients of finite metric spaces, Adv. Math., Volume 189 (2004), pp. 451-494 | Zbl | DOI
[45.] Metric cotype, Ann. Math., Volume 168 (2008), pp. 247-298 | Zbl | DOI
[46.] M. Mendel and A. Naor, Expanders with respect to Hadamard spaces and random graphs, preprint (2012).
[47.] M. Mendel and A. Naor, Spectral calculus and Lipschitz extension for barycentric metric spaces, preprint (2013). Available at | arXiv | Zbl
[48.] Transformations de Riesz pour les lois gaussiennes, Seminar on Probability, XVIII (1984), pp. 179-193 | Zbl | Numdam
[49.] Asymptotic Theory of Finite-Dimensional Normed Spaces (1986) | Zbl
[50.] L1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry, Proceedings of the International Congress of Mathematicians (2010), pp. 1549-1575 | Zbl
[51.] An introduction to the Ribe program, Jpn. J. Math., Volume 7 (2012), pp. 167-233 | Zbl | DOI
[52.] On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon–Roichman graphs, Comb. Probab. Comput., Volume 21 (2012), pp. 611-622 | Zbl | DOI
[53.] A. Naor and Y. Rabani, Spectral inequalities on curved spaces, preprint (2005).
[54.] Remarks on non linear type and Pisier’s inequality, J. Reine Angew. Math., Volume 552 (2002), pp. 213-236 | Zbl
[55.] Absolutely minimal Lipschitz extension of tree-valued mappings, Math. Ann., Volume 354 (2012), pp. 1049-1078 | Zbl | DOI
[56.] Poincaré inequalities, embeddings, and wild groups, Compos. Math., Volume 147 (2011), pp. 1546-1572 | Zbl | DOI
[57.] A note on non-amenability of =1,2, Int. J. Math., Volume 15 (2004), pp. 557-565 | Zbl | DOI
[58.] On quasi-metric and metric spaces, Proc. Am. Math. Soc., Volume 137 (2009), pp. 4307-4312 | Zbl | DOI
[59.] Martingales with values in uniformly convex spaces, Isr. J. Math., Volume 20 (1975), pp. 326-350 | Zbl | DOI
[60.] Some applications of the complex interpolation method to Banach lattices, J. Anal. Math., Volume 35 (1979), pp. 264-281 | Zbl | DOI
[61.] Holomorphic semigroups and the geometry of Banach spaces, Ann. Math., Volume 115 (1982), pp. 375-392 | Zbl | DOI
[62.] G. Pisier, A remark on hypercontractive semigroups and operator ideals, preprint (2007). Available at | arXiv
[63.] Complex interpolation between Hilbert, Banach and operator spaces, Mem. Am. Math. Soc., Volume 208 (2010), p. vi+78 | Zbl
[64.] Random series in the real interpolation spaces between the spaces vp, Geometrical Aspects of Functional Analysis (1985/86) (1987), pp. 185-209 | Zbl
[65.] Lower bounds on the distortion of embedding finite metric spaces in graphs, Discrete Comput. Geom., Volume 19 (1998), pp. 79-94 | Zbl | DOI
[66.] Pseudorandom walks on regular digraphs and the RL vs. L problem, STOC (2006), pp. 457-466 | Zbl
[67.] Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. Math., Volume 155 (2002), pp. 157-187 | Zbl | DOI
[68.] Lectures on Coarse Geometry (2003) | Zbl
[69.] Derandomized squaring of graphs, Approximation, Randomization and Combinatorial Optimization (2005), pp. 436-447 | Zbl
[70.] Banach Spaces for Analysts (1991) | Zbl
[71.] The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space, Invent. Math., Volume 139 (2000), pp. 201-240 | Zbl | DOI
Cited by Sources: