×

zbMATH — the first resource for mathematics

Ramanujan complexes and high dimensional expanders. (English) Zbl 1302.05095
Summary: Expander graphs in general, and Ramanujan graphs in particular, have been of great interest in the last four decades with many applications in computer science, combinatorics and even pure mathematics. In these notes we describe various efforts made in recent years to generalize these notions from graphs to higher dimensional simplicial complexes.

MSC:
05C40 Connectivity
05C42 Density (toughness, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
22E35 Analysis on \(p\)-adic Lie groups
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alon, N., Eigenvalues and expanders, Combinatorica., 6, 83-96, (1986) · Zbl 0661.05053
[2] Alon, N.; Milman V., D., \({λ_1}\), isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B., 38, 73-88, (1985) · Zbl 0549.05051
[3] Ballantine, C.M., Ramanujan type buildings, Canad. J. Math., 52, 1121-1148, (2000) · Zbl 0999.20019
[4] Bárány, I., A generalization of carathéodory’s theorem, Discrete Math., 40, 141-152, (1982) · Zbl 0492.52005
[5] Borel, A., Cohomologie de certains groupes discretes et laplacien \(p\)-adique, Séminaire Bourbaki., 437, 12-35, (1973)
[6] Boros, E.; Füredi, Z., The number of triangles covering the center of an \(n\)-set, Geom. Dedicata., 17, 69-77, (1984) · Zbl 0595.52002
[7] P. Cartier, Representations of \(p\)-adic groups: a survey, In: Automorphic Forms, Representations and \(L\)-functions. Part 1, Proc. Sympos. Pure Math., 33, Amer. Math. Soc., Providence, RI, 1979, pp. 111-155. · Zbl 1305.55010
[8] Cartwright, D.I.; Steger, T., A family of \({\tilde{A}_{n}}\) -groups, Israel J. Math.,, 103, 125-140, (1998) · Zbl 0923.51010
[9] Cartwright, D.I.; Solé, P.; Żuk, A, Ramanujan geometries of type \({\tilde{A}_n}\)., Discrete Math., 269, 35-43, (2003) · Zbl 1021.05068
[10] Deitmar, A.; Hoffman, J.W., The ihara-Selberg zeta function for PGL_{3} and Hecke operators, Internat. J. Math., 17, 143-155, (2006) · Zbl 1200.11069
[11] A. Deitmar and M.H. Kang, Geometric zeta functions for higher rank \(p\)-adic groups, preprint, arXiv:1303.6848. · Zbl 1377.11102
[12] Dotterrer, D.; Kahle, M., Coboundary expanders, J. Topol. Anal., 4, 499-514, (2012) · Zbl 1259.05151
[13] Dodziuk, J., Difference equations, isoperimetric inequality and transience of certain random walks. trans, Amer. Math. Soc., 284, 787-794, (1984) · Zbl 0512.39001
[14] Drinfel’d, V.G., Proof of the Petersson conjecture for \({{\rm GL}\left(2\right)}\) over a global field of characteristic \(p\), Funct. Anal. Appl., 22, 28-43, (1988) · Zbl 0662.12012
[15] S. Evra, Geometric overlap of finite quotients of Bruhat-Tits buildings, M.Sc. thesis, Hebrew Univ., Jerusalem, 2014. · Zbl 1358.05075
[16] S. Evra, K. Golubev and A. Lubotzky, Mixing properties and the chromatic number of Ramanujan complexes, preprint. · Zbl 1328.05208
[17] U. First, Optimal spectrum in simplicial complexes, in preparation.
[18] Fox, J.; Gromov, M.; Lafforgue, V.; Naor, A.; Pach, J., Overlap properties of geometric expanders. J. reine angew, Math., 671, 49-83, (2012) · Zbl 1306.05171
[19] Garland, H., \(p\)-adic curvature and the cohomology of discrete subgroups of \(p\)-adic groups., Ann. of Math., 97, 375-423, (1973) · Zbl 0262.22010
[20] K. Golubev and O. Parzanchevski, Spectrum and combinatorics of Ramanujan triangle complexes, preprint. · Zbl 1410.05126
[21] Gromov, M., Singularities, expanders and topology of maps. part 2: from combinatorics to topology via algebraic isoperimetry, Geom. Funct Anal., 20, 416-526, (2010) · Zbl 1251.05039
[22] A. Gundert and M. Szedlák, Higher dimensional discrete Cheeger inequalities, In: Proceedings of the 30th Annual Symposium on Computational Geometry, to appear (2014). · Zbl 1395.05100
[23] A. Gundert and U. Wagner, On Laplacians of random complexes, In: Computational Geometry (SCG’12), Proceedings of the 28th Annual ACM Symposium, ACM, New York, 2012, pp. 151-160. · Zbl 1293.05210
[24] K. Hashimoto, Zeta functions of finite graphs and representations of \(p\)-adic groups, In: Automorphic Forms and Geometry of Arithmetic Varieties, Adv. Stud. Pure Math., 15, Academic Press, Boston, MA, 1989, pp. 211-280. · Zbl 0814.68098
[25] Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.), 43, 439-561, (2006) · Zbl 1147.68608
[26] Ihara, Y., On discrete subgroups of the two by two projective linear group over \({\mathfrak{p}}\) -adic fields, J. Math. Soc. Japan,, 18, 219-235, (1966) · Zbl 0158.27702
[27] Kang, M.-H.; Li, W.-C.W., Zeta functions of complexes arising from PGL(3), Adv. Math., 256, 46-103, (2014) · Zbl 1328.22008
[28] Kang, M.-H.; Li, W.-C.W.; Wang, C.-J., The zeta functions of complexes from PGL(3): a representation-theoretic approach, Israel J. Math., 177, 335-348, (2010) · Zbl 1230.05286
[29] Karasev, R., A simpler proof of the boros-Füredi-Bárány-pach-Gromov theorem, Discrete Comput. Geom., 47, 492-495, (2012) · Zbl 1237.05054
[30] T. Kaufman, D. Kazhdan and A. Lubotzky, Higher dimensional expanders, Ramanujan complexes and topological overlapping, preprint. · Zbl 1339.05075
[31] T. Kaufman and A. Lubotzky, Edge transitive Ramanujan graphs and symmetric LDPC good codes, In: STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 359-366. · Zbl 1286.94102
[32] T. Kaufman and A. Lubotzky, High dimensional expanders and property testing, In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ACM, New York, 2014, pp. 501-506. · Zbl 1365.68462
[33] T. Kaufman and U. Wagner, in preparation. · Zbl 0092.33503
[34] Kesten, H., Symmetric random walks on groups, Trans. Amer. Math. Soc., 92, 336-354, (1959) · Zbl 0092.33503
[35] Lafforgue, L., Chtoucas de Drinfeld et correspondance de Langlands, Invent. Math., 147, 1-241, (2002) · Zbl 1038.11075
[36] Li, W.-C.W., Ramanujan hypergraphs, Geom. Funct. Anal., 14, 380-399, (2004) · Zbl 1084.05047
[37] Linial, N.; Meshulam, R., Homological connectivity of random 2-complexes, Combinatorica., 26, 475-487, (2006) · Zbl 1121.55013
[38] Lubotzky, A., On finite index subgroups of linear groups, Bull. London Math. Soc., 19, 325-328, (1987) · Zbl 0597.20043
[39] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Progr. Math., 125, Birkhäuser, Besel, 1994. · Zbl 0826.22012
[40] Lubotzky, A., Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc. (N.S.)., 49, 113-162, (2012) · Zbl 1232.05194
[41] Lubotzky, A.; Meshulam, R., A Moore bound for simplicial complexes, Bull. Lond. Math. Soc., 39, 353-358, (2007) · Zbl 1180.13028
[42] A. Lubotzky and R. Meshulam, Random Latin squares and 2-dimensional expanders, preprint, arXiv:1307.3582. · Zbl 1306.05020
[43] A. Lubotzky, R. Meshulam and S. Mozes, Expansion of building-like complexes, preprint. · Zbl 1405.55019
[44] Lubotzky, A.; Phillips, R.; Sarnak, P, Ramanujan graphs, Combinatorica., 8, 261-277, (1988) · Zbl 0661.05035
[45] Lubotzky, A.; Samuels, B.; Vishne, U., Ramanujan complexes of type \({\tilde{A}_{d}}\), Israel J. Math., 149, 267-299, (2005) · Zbl 1087.05036
[46] Lubotzky, A.; Samuels, B.; Vishne, U., Explicit constructions of Ramanujan complexes of type \({\tilde{A}_{d}}\), European J, Combin., 26, 965-993, (2005) · Zbl 1135.05038
[47] I.G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Math. Monogr., Clarendon Press, Oxford Univ. Press, New York, 1979. · Zbl 0487.20007
[48] A. Marcus, D.A. Spielman and N. Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, preprint, arXiv:1304.4132. · Zbl 1316.05066
[49] Margulis, G.A., Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii., 24, 51-60, (1988)
[50] J. Matoušek and U. Wagner, On Gromov’s method of selecting heavily covered points, preprint, arXiv:1102.3515; Discrete Comput. Geom., to appear (2014). · Zbl 1200.11069
[51] Meshulam, R.; Wallach, N, Homological connectivity of random \(k\)-dimensional complexes., Random Structures Algorithms., 34, 408-417, (2009) · Zbl 1177.55011
[52] Mohammadi, A.; Salehi Golsefidy, A., Discrete subgroups acting transitively on vertices of a Bruhat-Tits building, duke math, J., 161, 483-544, (2012) · Zbl 1254.22015
[53] Morgenstern, M., Existence and explicit constructions of \(q\) + 1 regular Ramanujan graphs for every prime power \(q\), J. Combin. Theory Ser. B., 62, 44-62, (1994) · Zbl 0814.68098
[54] Morgenstern, M., Ramanujan diagrams, SIAM J. Discrete Math., 7, 560-570, (1994) · Zbl 0811.05045
[55] Morgenstern, M., Natural bounded concentrators, Combinatorica, 15, 111-122, (1995) · Zbl 0822.05038
[56] Newman, I.; Rabinovich, Y., On multiplicative \({λ}\) -approximations and some geometric applications, SIAM J. Comput., 42, 855-883, (2013) · Zbl 1281.28006
[57] Nilli, A., On the second eigenvalue of a graph, Discrete Math., 91, 207-210, (1991) · Zbl 0771.05064
[58] Pach J., A, Tverberg-type result on multicolored simplices, Comput. Geom., 10, 71-76, (1998) · Zbl 0896.68143
[59] O. Parzanchevski, Mixing in high-dimensional expanders, preprint, arXiv:1310.6477. · Zbl 1371.05329
[60] O. Parzanchevski and R. Rosenthal, Simplicial complexes: spectrum, homology and random walks, preprint, arXiv:1211.6775. · Zbl 1359.05114
[61] O. Parzanchevski, R. Rosenthal and R.J. Tessler, Isoperimetric inequalities in simplicial complexes, preprint, arXiv:1207.0638. · Zbl 1389.05174
[62] Samuels, B., On non-uniform Ramanujan complexes, Proc. Amer. Math. Soc., 137, 2869-2877, (2009) · Zbl 1279.11053
[63] P. Sarnak, Some Applications of Modular Forms, Cambridge Tracts in Math., 99, Cambridge Univ. Press, Cambridge, 1990. · Zbl 0771.05064
[64] Sarveniazi A. (2007) Explicit construction of a Ramanujan \({\left(n_{1},n_{2},…,n_{d-1}\right)}\) -regular hypergraph. Duke Math. J., 139, 141-171 · Zbl 1180.11016
[65] I. Satake, Spherical functions and Ramanujan conjecture, In: Algebraic Groups and Discontinous: Subgroups, Proc. Sympos. Pure Math., 9, Amer. Math. Soc., Providence, RI, 1966, pp. 258-264. · Zbl 1180.13028
[66] J.P. Serre, Trees, Springer-Verlag, 1980. · Zbl 0548.20018
[67] Steenbergen, J.; Klivans, C.; Mukherjee, S, A Cheeger-type inequality on simplicial complexes. adv. in appl, Math., 56, 56-77, (2014) · Zbl 1305.55010
[68] K., Storm, The zeta function of a hypergraph, Electron. J. Combin.,, 13, r84, (2006) · Zbl 1112.05072
[69] T. Sunada, Fundamental groups and Laplacians, In: Geometry and Analysis on Manifolds, Lecture Notes in Math., 1339, Springer-Verlag, 1988, pp. 248-277.
[70] Tanner, R.M., Explicit concentrators from generalized \(N\)-gons, SIAM J. Algebraic Discrete Methods., 5, 287-293, (1984) · Zbl 0554.05045
[71] Valette, A., Graphes de Ramanujan et applications, Astérisque., 245, 247-276, (1997) · Zbl 0929.05042
[72] U. Wagner, Minors in random and expanding hypergraphs, In: Computational Geometry (SCG’11), Proceedings of the 27th Annual Symposium, AMC, New York, 2011, pp. 351-360. · Zbl 1283.05196
[73] Zuk, A., La propriété (T) de Kazhdan pour LES groupes agissant sur LES polyedres. C. R, Acad. Sci. Paris Sér. I Math., 323, 453-458, (1996) · Zbl 0858.22007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.