Bounded degree cosystolic expanders of every dimension

Evra, Shai; Kaufman, Tali

doi:10.1090/jams/1019

Bounded degree cosystolic expanders of every dimension
HTML articles powered by AMS MathViewer

by Shai Evra and Tali Kaufman;

J. Amer. Math. Soc. 37 (2024), 39-68

DOI: https://doi.org/10.1090/jams/1019

Published electronically: July 21, 2023

HTML | PDF | Request permission

Abstract:

In this work we present a new local to global criterion for proving a form of high dimensional expansion, which we term cosystolic expansion. Applying this criterion on Ramanujan complexes yields for every dimension an infinite family of bounded degree complexes with the topological overlap property. This answers an open question raised by Gromov.

References

Peter Abramenko and Kenneth S. Brown, Buildings, Graduate Texts in Mathematics, vol. 248, Springer, New York, 2008. Theory and applications. MR 2439729, DOI 10.1007/978-0-387-78835-7
Imre Bárány, A generalization of Carathéodory’s theorem, Discrete Math. 40 (1982), no. 2-3, 141–152. MR 676720, DOI 10.1016/0012-365X(82)90115-7
E. Boros and Z. Füredi, The number of triangles covering the center of an $n$-set, Geom. Dedicata 17 (1984), no. 1, 69–77. MR 771183, DOI 10.1007/BF00181519
Y. M. Barzdin and A. N. Kolmogorov, On the realization of nets in 3-dimensional space, Probl. Cybernet, 8: 261-268, (1967). See also Selected Works of A.N. Kolmogorov, Kluwer Academic Publishers, 3: 194-202,245, (1993).
Dominic Dotterrer and Matthew Kahle, Coboundary expanders, J. Topol. Anal. 4 (2012), no. 4, 499–514. MR 3021774, DOI 10.1142/S1793525312500197
Dominic Dotterrer, Tali Kaufman, and Uli Wagner, On expansion and topological overlap, Geom. Dedicata 195 (2018), 307–317. MR 3820508, DOI 10.1007/s10711-017-0291-4
Shai Evra, Finite quotients of Bruhat-Tits buildings as geometric expanders, J. Topol. Anal. 9 (2017), no. 1, 51–66. MR 3594606, DOI 10.1142/S1793525317500078
Shai Evra, Konstantin Golubev, and Alexander Lubotzky, Mixing properties and the chromatic number of Ramanujan complexes, Int. Math. Res. Not. IMRN 22 (2015), 11520–11548. MR 3456695, DOI 10.1093/imrn/rnv022
Lior Eldar, Maris Ozols, and Kevin Thompson, The need for structure in quantum LDPC codes, IEEE Trans. Inform. Theory 66 (2020), no. 3, 1460–1473. MR 4077499, DOI 10.1109/tit.2019.2952366
Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor, and János Pach, Overlap properties of geometric expanders, J. Reine Angew. Math. 671 (2012), 49–83. MR 2983197, DOI 10.1515/crelle.2011.157
Howard Garland, $p$-adic curvature and the cohomology of discrete subgroups of $p$-adic groups, Ann. of Math. (2) 97 (1973), 375–423. MR 320180, DOI 10.2307/1970829
Mikhail Gromov, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geom. Funct. Anal. 20 (2010), no. 2, 416–526. MR 2671284, DOI 10.1007/s00039-010-0073-8
Misha Gromov and Larry Guth, Generalizations of the Kolmogorov-Barzdin embedding estimates, Duke Math. J. 161 (2012), no. 13, 2549–2603. MR 2988903, DOI 10.1215/00127094-1812840
Larry Guth and Alexander Lubotzky, Quantum error correcting codes and 4-dimensional arithmetic hyperbolic manifolds, J. Math. Phys. 55 (2014), no. 8, 082202, 13. MR 3390717, DOI 10.1063/1.4891487
Anna Gundert and May Szedlák, Higher dimensional discrete Cheeger inequalities, J. Comput. Geom. 6 (2015), no. 2, 54–71. MR 3305828, DOI 10.20382/jocg.v6i2a4
Anna Gundert and Uli Wagner, On Laplacians of random complexes, Computational geometry (SCG’12), ACM, New York, 2012, pp. 151–160. MR 3024710, DOI 10.1145/2261250.2261272
Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919, DOI 10.1090/S0273-0979-06-01126-8
Tali Kaufman, David Kazhdan, and Alexander Lubotzky, Isoperimetric inequalities for Ramanujan complexes and topological expanders, Geom. Funct. Anal. 26 (2016), no. 1, 250–287. MR 3494490, DOI 10.1007/s00039-016-0362-y
Tali Kaufman and David Mass, High dimensional random walks and colorful expansion, 8th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 4, 27. MR 3754928
T. Kaufman and D. Mass, Walking on the edge and cosystolic expansion, Preprint, arXiv:1606.01844, 2016.
T. Kaufman and D. Mass, Cosystolic expanders over any abelian group, Electron. Colloq. Comput. Complexity, 24 (2018), 134.
Tali Kaufman and David Mass, Unique-neighbor-like expansion and group-independent cosystolic expansion, 32nd International Symposium on Algorithms and Computation, LIPIcs. Leibniz Int. Proc. Inform., vol. 212, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 56, 17. MR 4418604
Antti Knowles and Ron Rosenthal, Eigenvalue confinement and spectral gap for random simplicial complexes, Random Structures Algorithms 51 (2017), no. 3, 506–537. MR 3689342, DOI 10.1002/rsa.20710
Alexander Lubotzky, Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc. (N.S.) 49 (2012), no. 1, 113–162. MR 2869010, DOI 10.1090/S0273-0979-2011-01359-3
Alexander Lubotzky, Ramanujan complexes and high dimensional expanders, Jpn. J. Math. 9 (2014), no. 2, 137–169. MR 3258617, DOI 10.1007/s11537-014-1265-z
Alexander Lubotzky, High dimensional expanders, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. I. Plenary lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 705–730. MR 3966743
Nathan Linial and Roy Meshulam, Homological connectivity of random 2-complexes, Combinatorica 26 (2006), no. 4, 475–487. MR 2260850, DOI 10.1007/s00493-006-0027-9
Alexander Lubotzky and Roy Meshulam, Random Latin squares and 2-dimensional expanders, Adv. Math. 272 (2015), 743–760. MR 3303247, DOI 10.1016/j.aim.2014.12.015
Alexander Lubotzky, Roy Meshulam, and Shahar Mozes, Expansion of building-like complexes, Groups Geom. Dyn. 10 (2016), no. 1, 155–175. MR 3460334, DOI 10.4171/GGD/346
Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Ramanujan complexes of type $\~A_d$, Israel J. Math. 149 (2005), 267–299. Probability in mathematics. MR 2191217, DOI 10.1007/BF02772543
Alexander Lubotzky, Beth Samuels, and Uzi Vishne, Explicit constructions of Ramanujan complexes of type $\~A_d$, European J. Combin. 26 (2005), no. 6, 965–993. MR 2143204, DOI 10.1016/j.ejc.2004.06.007
Alexander Lubotzky, Zur Luria, and Ron Rosenthal, Random Steiner systems and bounded degree coboundary expanders of every dimension, Discrete Comput. Geom. 62 (2019), no. 4, 813–831. MR 4027617, DOI 10.1007/s00454-018-9991-2
R. Meshulam and N. Wallach, Homological connectivity of random $k$-dimensional complexes, Random Structures Algorithms 34 (2009), no. 3, 408–417. MR 2504405, DOI 10.1002/rsa.20238
Hee Oh, Uniform pointwise bounds for matrix coefficients of unitary representations and applications to Kazhdan constants, Duke Math. J. 113 (2002), no. 1, 133–192. MR 1905394, DOI 10.1215/S0012-7094-02-11314-3
Izhar Oppenheim, Local spectral expansion approach to high dimensional expanders Part I: Descent of spectral gaps, Discrete Comput. Geom. 59 (2018), no. 2, 293–330. MR 3755725, DOI 10.1007/s00454-017-9948-x
Ori Parzanchevski, Mixing in high-dimensional expanders, Combin. Probab. Comput. 26 (2017), no. 5, 746–761. MR 3681980, DOI 10.1017/S0963548317000116
Ori Parzanchevski, Ron Rosenthal, and Ran J. Tessler, Isoperimetric inequalities in simplicial complexes, Combinatorica 36 (2016), no. 2, 195–227. MR 3516884, DOI 10.1007/s00493-014-3002-x
Ori Parzanchevski and Ron Rosenthal, Simplicial complexes: spectrum, homology and random walks, Random Structures Algorithms 50 (2017), no. 2, 225–261. MR 3607124, DOI 10.1002/rsa.20657
R. Rosenthal, Simplicial branching random walks and their applications, Preprint, arXiv:1412.5406, (2014).