Nonlinear spectral calculus and super-expanders
Publications Mathématiques de l'IHÉS, Tome 119 (2014), pp. 1-95.

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.

DOI : https://doi.org/10.1007/s10240-013-0053-2
MANUSCRIPT : 53
PUBLISHER-ID : s10240-013-0053-2
Mots clés : Banach Space, Regular Graph, Graph Product, Base Graph, Expander Graph
@article{PMIHES_2014__119__1_0,
     author = {Mendel, Manor and Naor, Assaf},
     title = {Nonlinear spectral calculus and super-expanders},
     journal = {Publications Math\'ematiques de l'IH\'ES},
     pages = {1--95},
     publisher = {Springer Berlin Heidelberg},
     address = {Berlin/Heidelberg},
     volume = {119},
     year = {2014},
     doi = {10.1007/s10240-013-0053-2},
     zbl = {1306.46021},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1007/s10240-013-0053-2/}
}
TY  - JOUR
AU  - Mendel, Manor
AU  - Naor, Assaf
TI  - Nonlinear spectral calculus and super-expanders
JO  - Publications Mathématiques de l'IHÉS
PY  - 2014
DA  - 2014///
SP  - 1
EP  - 95
VL  - 119
PB  - Springer Berlin Heidelberg
PP  - Berlin/Heidelberg
UR  - http://archive.numdam.org/articles/10.1007/s10240-013-0053-2/
UR  - https://zbmath.org/?q=an%3A1306.46021
UR  - https://doi.org/10.1007/s10240-013-0053-2
DO  - 10.1007/s10240-013-0053-2
LA  - en
ID  - PMIHES_2014__119__1_0
ER  - 
Mendel, Manor; Naor, Assaf. Nonlinear spectral calculus and super-expanders. Publications Mathématiques de l'IHÉS, Tome 119 (2014), pp. 1-95. doi : 10.1007/s10240-013-0053-2. http://archive.numdam.org/articles/10.1007/s10240-013-0053-2/

[1.] Alon, N.; Schwartz, O.; Shapira, A. An elementary construction of constant-degree expanders, Comb. Probab. Comput., Volume 17 (2008), pp. 319-327 | Article | Zbl 1194.05021

[2.] Alon, N.; Spencer, J. H. The Probabilistic Method (2008) | Zbl 1148.05001

[3.] Bader, U.; Furman, A.; Gelander, T.; Monod, N. Property (T) and rigidity for actions on Banach spaces, Acta Math., Volume 198 (2007), pp. 57-105 | Article | Zbl 1162.22005

[4.] Ball, K. Markov chains, Riesz transforms and Lipschitz maps, Geom. Funct. Anal., Volume 2 (1992), pp. 137-172 | Article | Zbl 0788.46050

[5.] Ball, K.; Carlen, E. A.; Lieb, E. H. Sharp uniform convexity and smoothness inequalities for trace norms, Invent. Math., Volume 115 (1994), pp. 463-482 | Article | Zbl 0803.47037

[6.] Bartal, Y.; Linial, N.; Mendel, M.; Naor, A. On metric Ramsey-type phenomena, Ann. Math., Volume 162 (2005), pp. 643-709 | Article | Zbl 1114.46007

[7.] Beckner, W. Inequalities in Fourier analysis, Ann. Math., Volume 102 (1975), pp. 159-182 | Article | Zbl 0338.42017

[8.] Bonami, A. Étude des coefficients de Fourier des fonctions de Lp(G), Ann. Inst. Fourier (Grenoble), Volume 20 (1971), pp. 335-402 | Article | Numdam | Zbl 0195.42501

[9.] Borovkov, A. A.; Utev, S. A. An inequality and a characterization of the normal distribution connected with it, Teor. Veroâtn. Ee Primen., Volume 28 (1983), pp. 209-218 | Zbl 0511.60016

[10.] Bourgain, J. On Lipschitz embedding of finite metric spaces in Hilbert space, Isr. J. Math., Volume 52 (1985), pp. 46-52 | Article | Zbl 0657.46013

[11.] Bridson, M. R.; Haefliger, A. Metric Spaces of Non-positive Curvature (1999) | Zbl 0988.53001

[12.] Cherix, P.-A.; Cowling, M.; Jolissaint, P.; Julg, P.; Valette, A. Groups with the Haagerup Property (2001) | Zbl 1030.43002

[13.] Chung, F. Diameters and eigenvalues, J. Am. Math. Soc., Volume 2 (1989), pp. 187-195 | Article | Zbl 0678.05037

[14.] Figiel, T. On the moduli of convexity and smoothness, Stud. Math., Volume 56 (1976), pp. 121-155 | Zbl 0344.46052

[15.] Figiel, T.; Pisier, G. 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 0326.46007

[16.] Garnett, J. B.; Marshall, D. E. Harmonic Measure (2008) | Zbl 1139.31001

[17.] Gromov, M. Filling Riemannian manifolds, J. Differ. Geom., Volume 18 (1983), pp. 1-147 | Zbl 0515.53037

[18.] Gromov, M. Asymptotic invariants of infinite groups, Geometric Group Theory, Vol. 2 (1993), pp. 1-295

[19.] Gromov, M. Random walk in random groups, Geom. Funct. Anal., Volume 13 (2003), pp. 73-146 | Article | Zbl 1122.20021

[20.] Guentner, E.; Higson, N.; Weinberger, S. The Novikov conjecture for linear groups, Publ. Math. Inst. Hautes Études Sci., Volume 101 (2005), pp. 243-268 | Article | Numdam | Zbl 1073.19003

[21.] Hoory, S.; Linial, N.; Wigderson, A. Expander graphs and their applications, Bull., New Ser., Am. Math. Soc., Volume 43 (2006), pp. 439-561 | Article | Zbl 1147.68608

[22.] James, R. C. A nonreflexive Banach space that is uniformly nonoctahedral, Isr. J. Math., Volume 18 (1974), pp. 145-155 | Article | Zbl 0292.46014

[23.] James, R. C. Nonreflexive spaces of type 2, Isr. J. Math., Volume 30 (1978), pp. 1-13 | Article | Zbl 0384.46004

[24.] James, R. C.; Lindenstrauss, J. 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 0307.46011

[25.] Kalton, N. J. The uniform structure of Banach spaces, Math. Ann., Volume 354 (2012), pp. 1247-1288 | Article | Zbl 1268.46018

[26.] Kalton, N. J.; Peck, N. T.; Roberts, J. W. An F-Space Sampler (1984) | Zbl 0556.46002

[27.] Kasparov, G.; Yu, G. The coarse geometric Novikov conjecture and uniform convexity, Adv. Math., Volume 206 (2006), pp. 1-56 | Article | Zbl 1102.19003

[28.] Khot, S.; Naor, A. Nonembeddability theorems via Fourier analysis, Math. Ann., Volume 334 (2006), pp. 821-852 | Article | Zbl 1102.46051

[29.] Lafforgue, V. Un renforcement de la propriété (T), Duke Math. J., Volume 143 (2008), pp. 559-602 | Article | Zbl 1158.46049

[30.] Lafforgue, V. Propriété (T) renforcée Banachique et transformation de Fourier rapide, J. Topol. Anal., Volume 1 (2009), pp. 191-206 | Article | Zbl 1186.46022

[31.] Lafforgue, V. Propriété (T) renforcée et conjecture de Baum-Connes, Quanta of Maths (2010), pp. 323-345 | Zbl 1216.19007

[32.] Ledoux, M. The Concentration of Measure Phenomenon (2001) | Zbl 0995.60002

[33.] Lindenstrauss, J. On the modulus of smoothness and divergent series in Banach spaces, Mich. Math. J., Volume 10 (1963), pp. 241-252 | Article | Zbl 0115.10001

[34.] Lindenstrauss, J.; Tzafriri, L. Classical Banach Spaces. II (1979) | Zbl 0403.46022

[35.] Linial, N.; London, E.; Rabinovich, Y. The geometry of graphs and some of its algorithmic applications, Combinatorica, Volume 15 (1995), pp. 215-245 | Article | Zbl 0827.05021

[36.] Lubotzky, A. Expander graphs in pure and applied mathematics, Bull., New Ser., Am. Math. Soc., Volume 49 (2012), pp. 113-162 | Article | Zbl 1232.05194

[37.] Lubotzky, A.; Phillips, R.; Sarnak, P. Ramanujan graphs, Combinatorica, Volume 8 (1988), pp. 261-277 | Article | Zbl 0661.05035

[38.] Macías, R. A.; Segovia, C. Lipschitz functions on spaces of homogeneous type, Adv. Math., Volume 33 (1979), pp. 257-270 | Article | Zbl 0431.46018

[39.] MacWilliams, F. J.; Sloane, N. J. A. The Theory of Error-Correcting Codes. I (1977) | Zbl 0369.94008

[40.] Margulis, G. A. 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 0708.05030

[41.] Matoušek, J. On embedding expanders into ℓp spaces, Isr. J. Math., Volume 102 (1997), pp. 189-197 | Article | Zbl 0947.46007

[42.] Maurey, B. Type, cotype and K-convexity, Handbook of the Geometry of Banach Spaces (2003), pp. 1299-1332 | Zbl 1074.46006

[43.] Maurey, B.; Pisier, G. 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 0344.47014

[44.] Mendel, M.; Naor, A. Euclidean quotients of finite metric spaces, Adv. Math., Volume 189 (2004), pp. 451-494 | Article | Zbl 1088.46007

[45.] Mendel, M.; Naor, A. Metric cotype, Ann. Math., Volume 168 (2008), pp. 247-298 | Article | Zbl 1187.46014

[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:1301.3963 | Zbl 1297.54037

[48.] Meyer, P.-A. Transformations de Riesz pour les lois gaussiennes, Seminar on Probability, XVIII (1984), pp. 179-193 | Zbl 0543.60078

[49.] Milman, V. D.; Schechtman, G. Asymptotic Theory of Finite-Dimensional Normed Spaces (1986) | Zbl 0911.52002

[50.] Naor, A. L1 embeddings of the Heisenberg group and fast estimation of graph isoperimetry, Proceedings of the International Congress of Mathematicians (2010), pp. 1549-1575 | Zbl 1232.46021

[51.] Naor, A. An introduction to the Ribe program, Jpn. J. Math., Volume 7 (2012), pp. 167-233 | Article | Zbl 1261.46013

[52.] Naor, A. On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon–Roichman graphs, Comb. Probab. Comput., Volume 21 (2012), pp. 611-622 | Article | Zbl 1247.05104

[53.] A. Naor and Y. Rabani, Spectral inequalities on curved spaces, preprint (2005).

[54.] Naor, A.; Schechtman, G. Remarks on non linear type and Pisier’s inequality, J. Reine Angew. Math., Volume 552 (2002), pp. 213-236 | Zbl 1033.46013

[55.] Naor, A.; Sheffield, S. Absolutely minimal Lipschitz extension of tree-valued mappings, Math. Ann., Volume 354 (2012), pp. 1049-1078 | Article | Zbl 1276.46062

[56.] Naor, A.; Silberman, L. Poincaré inequalities, embeddings, and wild groups, Compos. Math., Volume 147 (2011), pp. 1546-1572 | Article | Zbl 1267.20057

[57.] Ozawa, N. A note on non-amenability of ( l p ) for p = 1 , 2 , =1,2, Int. J. Math., Volume 15 (2004), pp. 557-565 | Article | Zbl 1056.46046

[58.] Paluszyński, M.; Stempak, K. On quasi-metric and metric spaces, Proc. Am. Math. Soc., Volume 137 (2009), pp. 4307-4312 | Article | Zbl 1191.54022

[59.] Pisier, G. Martingales with values in uniformly convex spaces, Isr. J. Math., Volume 20 (1975), pp. 326-350 | Article | Zbl 0344.46030

[60.] Pisier, G. Some applications of the complex interpolation method to Banach lattices, J. Anal. Math., Volume 35 (1979), pp. 264-281 | Article | Zbl 0427.46048

[61.] Pisier, G. Holomorphic semigroups and the geometry of Banach spaces, Ann. Math., Volume 115 (1982), pp. 375-392 | Article | Zbl 0487.46008

[62.] G. Pisier, A remark on hypercontractive semigroups and operator ideals, preprint (2007). Available at | arXiv:0708.3423

[63.] Pisier, G. Complex interpolation between Hilbert, Banach and operator spaces, Mem. Am. Math. Soc., Volume 208 (2010), p. vi+78 | Zbl 1213.46002

[64.] Pisier, G.; Xu, Q. H. Random series in the real interpolation spaces between the spaces vp, Geometrical Aspects of Functional Analysis (1985/86) (1987), pp. 185-209 | Zbl 0634.46009

[65.] Rabinovich, Y.; Raz, R. Lower bounds on the distortion of embedding finite metric spaces in graphs, Discrete Comput. Geom., Volume 19 (1998), pp. 79-94 | Article | Zbl 0890.05021

[66.] Reingold, O.; Trevisan, L.; Vadhan, S. P. Pseudorandom walks on regular digraphs and the RL vs. L problem, STOC (2006), pp. 457-466 | Zbl 1301.05317

[67.] Reingold, O.; Vadhan, S.; Wigderson, A. Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. Math., Volume 155 (2002), pp. 157-187 | Article | Zbl 1008.05101

[68.] Roe, J. Lectures on Coarse Geometry (2003) | Zbl 1042.53027

[69.] Rozenman, E.; Vadhan, S. Derandomized squaring of graphs, Approximation, Randomization and Combinatorial Optimization (2005), pp. 436-447 | Zbl 1142.05331

[70.] Wojtaszczyk, P. Banach Spaces for Analysts (1991) | Zbl 0724.46012

[71.] Yu, G. The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space, Invent. Math., Volume 139 (2000), pp. 201-240 | Article | Zbl 0956.19004

Cité par Sources :