Nonlinear spectral calculus and super-expanders

Mendel, Manor; Naor, Assaf

doi:10.1007/s10240-013-0053-2

Mendel, Manor ¹ ; Naor, Assaf ²

¹ Mathematics and Computer Science Department, Open University of Israel P.O. Box 808 1 University Road 43107 Raanana Israel
² Courant Institute, New York University 251 Mercer Street 10012 New York NY USA

Publications Mathématiques de l'IHÉS, Tome 119 (2014), pp. 1-95.

Résumé

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.

Zbl | 1 citation dans Numdam

DOI : 10.1007/s10240-013-0053-2

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

Affiliations des auteurs :

Mendel, Manor ¹ ; Naor, Assaf ²

@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 = {https://www.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
SP  - 1
EP  - 95
VL  - 119
PB  - Springer Berlin Heidelberg
PP  - Berlin/Heidelberg
UR  - https://www.numdam.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 Mendel, Manor
%A Naor, Assaf
%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://www.numdam.org/articles/10.1007/s10240-013-0053-2/
%R 10.1007/s10240-013-0053-2
%G en
%F PMIHES_2014__119__1_0

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. https://www.numdam.org/articles/10.1007/s10240-013-0053-2/

Bibliographie
Cité par

[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 $ℬ (l_{p}) 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

Fathi, Max; Gentil, Ivan; Serres, Jordan Stability estimates for the sharp spectral gap bound under a curvature-dimension condition, Annales de l'Institut Fourier, Volume 74 (2024) no. 6, p. 2425 | DOI:10.5802/aif.3608
Volberg, Alexander Tail spaces estimates on Hamming cube and Bernstein–Markov inequality, Journal of Mathematical Analysis and Applications, Volume 529 (2024) no. 2, p. 127597 | DOI:10.1016/j.jmaa.2023.127597
Baudier, Florent P.; Braga, Bruno M.; Farah, Ilijas; Vignati, Alessandro; Willett, Rufus Coarse equivalence versus bijective coarse equivalence of expander graphs, Mathematische Zeitschrift, Volume 307 (2024) no. 3 | DOI:10.1007/s00209-024-03512-w
Cordero-Erausquin, Dario; Eskenazis, Alexandros Talagrand’s influence inequality revisited, Analysis PDE, Volume 16 (2023) no. 2, p. 571 | DOI:10.2140/apde.2023.16.571
Oppenheim, Izhar Banach property (T) for ${SL}_{n} (Z)$ and its applications, Inventiones mathematicae, Volume 234 (2023) no. 2, p. 893 | DOI:10.1007/s00222-023-01211-7
Eskenazis, Alexandros; Ivanisvili, Paata Sharp growth of the Ornstein—Uhlenbeck operator on Gaussian tail spaces, Israel Journal of Mathematics, Volume 253 (2023) no. 1, p. 469 | DOI:10.1007/s11856-022-2373-8
Zhang, Haonan Heat-smoothing for holomorphic subalgebras of free group von Neumann algebras, Proceedings of the American Mathematical Society (2023) | DOI:10.1090/proc/16367
Chen, Jun Xi; Cheng, Qing Jin On Quantitative Sphere Equivalence and Extrapolation Phenomenon, Acta Mathematica Sinica, English Series, Volume 38 (2022) no. 4, p. 709 | DOI:10.1007/s10114-022-1346-5
Weighill, Thomas; Yamauchi, Takamitsu; Zava, Nicolò Coarse infinite-dimensionality of hyperspaces of finite subsets, European Journal of Mathematics, Volume 8 (2022) no. 1, p. 335 | DOI:10.1007/s40879-021-00515-3
Chen, Junxi; Cheng, Xiaoyu A note on Poincaré constants, Filomat, Volume 36 (2022) no. 16, p. 5463 | DOI:10.2298/fil2216463c
Ivanisvili, P; Nazarov, F On Weissler’s Conjecture on the Hamming Cube I, International Mathematics Research Notices, Volume 2022 (2022) no. 9, p. 6991 | DOI:10.1093/imrn/rnaa363
Arzhantseva, Goulnara; Biswas, Arindam Logarithmic girth expander graphs of $S L_{n} (F_{p})$ , Journal of Algebraic Combinatorics, Volume 56 (2022) no. 3, p. 691 | DOI:10.1007/s10801-022-01128-z
Baudier, F. P. Barycentric gluing and geometry of stable metrics, Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas, Volume 116 (2022) no. 1 | DOI:10.1007/s13398-021-01179-0
Naor, Assaf Impossibility of almost extension, Advances in Mathematics, Volume 384 (2021), p. 107761 | DOI:10.1016/j.aim.2021.107761
Khukhro, Ana; Li, Kang; Vigolo, Federico; Zhang, Jiawen On the structure of asymptotic expanders, Advances in Mathematics, Volume 393 (2021), p. 108073 | DOI:10.1016/j.aim.2021.108073
de Laat, Tim; de la Salle, Mikael Banach space actions and L2-spectral gap, Analysis PDE, Volume 14 (2021) no. 1, p. 45 | DOI:10.2140/apde.2021.14.45
Erdélyi, Tamás Turán-Type Reverse Markov Inequalities for Polynomials with Restricted Zeros, Constructive Approximation, Volume 54 (2021) no. 1, p. 35 | DOI:10.1007/s00365-020-09509-y
Naor, Assaf An average John theorem, Geometry Topology, Volume 25 (2021) no. 4, p. 1631 | DOI:10.2140/gt.2021.25.1631
Naor, Assaf; Pisier, Gilles; Schechtman, Gideon Impossibility of Dimension Reduction in the Nuclear Norm, Discrete Computational Geometry, Volume 63 (2020) no. 2, p. 319 | DOI:10.1007/s00454-019-00162-2
Willett, Rufus; Yu, Guoliang Higher Index Theory, 2020 | DOI:10.1017/9781108867351
Erdélyi, Tamás Reverse Markov- and Bernstein-type inequalities for incomplete polynomials, Journal of Approximation Theory, Volume 251 (2020), p. 105341 | DOI:10.1016/j.jat.2019.105341
Eskenazis, Alexandros; Ivanisvili, Paata Dimension independent Bernstein–Markov inequalities in Gauss space, Journal of Approximation Theory, Volume 253 (2020), p. 105377 | DOI:10.1016/j.jat.2020.105377
Eskenazis, Alexandros; Ivanisvili, Paata Polynomial inequalities on the Hamming cube, Probability Theory and Related Fields, Volume 178 (2020) no. 1-2, p. 235 | DOI:10.1007/s00440-020-00973-y
Fisher, David; Nguyen, Thang; van Limbeek, Wouter Rigidity of warped cones and coarse geometry of expanders, Advances in Mathematics, Volume 346 (2019), p. 665 | DOI:10.1016/j.aim.2019.02.015
Aparicio, Maria Paula Gomez; Julg, Pierre; Valette, Alain The Baum–Connes conjecture: an extended survey, Advances in Noncommutative Geometry (2019), p. 127 | DOI:10.1007/978-3-030-29597-4_3
de Laat, Tim; Vigolo, Federico Superexpanders from group actions on compact manifolds, Geometriae Dedicata, Volume 200 (2019) no. 1, p. 287 | DOI:10.1007/s10711-018-0371-0
Eskenazis, Alexandros; Mendel, Manor; Naor, Assaf Nonpositive curvature is not coarsely universal, Inventiones mathematicae, Volume 217 (2019) no. 3, p. 833 | DOI:10.1007/s00222-019-00878-1
Vigolo, Federico Discrete fundamental groups of warped cones and expanders, Mathematische Annalen, Volume 373 (2019) no. 1-2, p. 355 | DOI:10.1007/s00208-018-1768-7
de Laat, Tim; de la Salle, Mikael Approximation properties for noncommutative Lp -spaces of high rank lattices and nonembeddability of expanders, Journal für die reine und angewandte Mathematik (Crelles Journal), Volume 2018 (2018) no. 737, p. 49 | DOI:10.1515/crelle-2015-0043
Das, Kajal From the geometry of box spaces to the geometry and measured couplings of groups, Journal of Topology and Analysis, Volume 10 (2018) no. 02, p. 401 | DOI:10.1142/s1793525318500127
Andoni, Alexandr; Naor, Assaf; Nikolov, Aleksandar; Razenshteyn, Ilya; Waingarten, Erik, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (2018), p. 787 | DOI:10.1145/3188745.3188846
Khukhro, Ana; Valette, Alain Expanders and box spaces, Advances in Mathematics, Volume 314 (2017), p. 806 | DOI:10.1016/j.aim.2017.05.007
Gavinsky, Dmitry; Pudlák, Pavel Partition Expanders, Theory of Computing Systems, Volume 60 (2017) no. 3, p. 378 | DOI:10.1007/s00224-016-9738-5
Heilman, Steven; Mossel, Elchanan; Oleszkiewicz, Krzysztof Strong contraction and influences in tail spaces, Transactions of the American Mathematical Society, Volume 369 (2017) no. 7, p. 4843 | DOI:10.1090/tran/6916
NAOR, ASSAF; SCHECHTMAN, GIDEON METRIC INEQUALITIES, Forum of Mathematics, Pi, Volume 4 (2016) | DOI:10.1017/fmp.2016.1
Salle, Mikael de la Towards strong Banach property (T) for SL(3,ℝ), Israel Journal of Mathematics, Volume 211 (2016) no. 1, p. 105 | DOI:10.1007/s11856-015-1262-9
Mendel, Manor; Naor, Assaf Expanders with respect to Hadamard spaces and random graphs, Duke Mathematical Journal, Volume 164 (2015) no. 8 | DOI:10.1215/00127094-3119525
Kondo, Takefumi; Toyoda, Tetsu Uniform Estimates of Nonlinear Spectral Gaps, Graphs and Combinatorics, Volume 31 (2015) no. 5, p. 1517 | DOI:10.1007/s00373-014-1457-6
Lafforgue, Vincent; Naor, Assaf Vertical versus horizontal Poincaré inequalities on the Heisenberg group, Israel Journal of Mathematics, Volume 203 (2014) no. 1, p. 309 | DOI:10.1007/s11856-014-1088-x
Mendel, Manor; Naor, Assaf, Proceedings of the 5th conference on Innovations in theoretical computer science (2014), p. 353 | DOI:10.1145/2554797.2554829
Ding, Jian; Lee, James R.; Peres, Yuval Markov type and threshold embeddings, Geometric and Functional Analysis, Volume 23 (2013) no. 4, p. 1207 | DOI:10.1007/s00039-013-0234-7

Cité par 41 documents. Sources : Crossref