Nonlinear spectral calculus and super-expanders

Mendel, Manor; Naor, Assaf

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.

Mots clés : Banach Space, Regular Graph, Graph Product, Base Graph, Expander Graph

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

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

[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 | DOI | Zbl

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

[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 | DOI | Zbl

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

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

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

[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

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

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

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

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

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

[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

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

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

[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 | DOI | Zbl

[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 | DOI | Numdam | Zbl

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

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

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

[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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[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

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

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

[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

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

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

[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.] Meyer, P.-A. Transformations de Riesz pour les lois gaussiennes, Seminar on Probability, XVIII (1984), pp. 179-193 | Numdam | Zbl

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

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

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

[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 | DOI | Zbl

[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

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

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

[57.] Ozawa, N. A note on non-amenability of $ℬ\left(l_p\right)\mathrm{for}p=1,2,$=1,2, Int. J. Math., Volume 15 (2004), pp. 557-565 | DOI | Zbl

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

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

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

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

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

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

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

[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 | DOI | Zbl

[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

[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 | DOI | Zbl

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

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

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

[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 | DOI | Zbl