×

zbMATH — the first resource for mathematics

Spectrum and combinatorics of two-dimensional Ramanujan complexes. (English) Zbl 1410.05126
Summary: Ramanujan graphs have extremal spectral properties, which imply a remarkable combinatorial behavior. In this paper we compute the high dimensional Hodge-Laplace spectrum of Ramanujan triangle complexes, and show that it implies a combinatorial expansion property, and a pseudorandomness result. For this purpose we prove a Cheeger-type inequality and a mixing lemma of independent interest.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alon, N.; Chung, F. R. K., Explicit construction of linear sized tolerant networks, Discrete Mathematics, 72, 15-19, (1988) · Zbl 0657.05068
[2] Alon, N.; Milman, V. D., No article title, λ1, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory. Series B, 38, 73-88, (1985) · Zbl 0549.05051
[3] Borel, A., Admissible representations of a semi-simple group over a local field with vectors fixed under an Iwahori subgroup, Inventiones Mathematicae, 35, 233-259, (1976) · Zbl 0334.22012
[4] Casselman, W., On a p-adic vanishing theorem of Garland, Bulletin of the American Mathematical Society, 80, 1001-1004, (1974) · Zbl 0354.20033
[5] Casselman, W., The unramified principal series of p-adic groups. I. The spherical function, Compositio Mathematica, 40, 387-406, (1980) · Zbl 0472.22004
[6] Cowling, M.; Haagerup, U.; Howe, R., Almost \(L\)2 matrix coefficients, Journal für die Reine und Angewandte Mathematik, 387, 97-110, (1988) · Zbl 0638.22004
[7] Cartwright, D. I.; Steger, T., Elementary symmetric polynomials in numbers of modulus 1, Canadian Journal of Mathematics, 54, 239-262, (2002) · Zbl 1006.05059
[8] Cartwright, D. I.; Solé, P.; Żuk, A., Ramanujan geometries of type A˜n, Discrete Mathematics, 269, 35-43, (2003) · Zbl 1021.05068
[9] B. Eckmann, Harmonische funktionen und randwertaufgaben in einem komplex, Commentarii Mathematici Helvetici 17 (1944), 240-255. · Zbl 0061.41106
[10] Evra, S.; Golubev, K.; Lubotzky, A., Mixing properties and the chromatic number of Ramanujan complexes, International Mathematics Research Notices, 22, 11520-11548, (2015) · Zbl 1328.05208
[11] Fox, J.; Gromov, M.; Lafforgue, V.; Naor, A.; Pach, J., Overlap properties of geometric expanders, Journal für die Reine und Angewandte Mathematik, 671, 49-83, (2012) · Zbl 1306.05171
[12] U. A. First, The Ramanujan property for simplicial complexes, preprint, arXiv:1605.02664.
[13] Friedman, J.; Pippenger, N., Expanding graphs contain all small trees, Combinatorica, 7, 71-76, (1987) · Zbl 0624.05028
[14] Garland, H., No article title, p-adic curvature and the cohomology of discrete subgroups of p-adic groups, Annals of Mathematics, 97, 375-423, (1973)
[15] Gundert, A.; Szedlák, M., Higher dimensional Cheeger inequalities, (2014), New York · Zbl 1395.05100
[16] A. Gundert and U. Wagner, On expansion and spectral properties of simplicial complexes, Ph.D. thesis, ETH Zürich, Switzerland, 2013, Diss. ETH No. 21600 of Anna Gundert. · Zbl 1337.55023
[17] Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bulletin of the American Mathematical Society, 43, 439-562, (2006) · Zbl 1147.68608
[18] Hoffman, A. J., On eigenvalues and colorings of graphs, (1970), Madison, Wis. · Zbl 0227.05105
[19] Kang, M. H.; Li, W. C. W.; Wang, C. J., The zeta functions of complexes from PGL(3): a representation-theoretic approach, Israel Journal of Mathematics, 177, 335-348, (2010) · Zbl 1230.05286
[20] Li, W. C. W., Ramanujan hypergraphs, Geometric and Functional Analysis, 14, 380-399, (2004) · Zbl 1084.05047
[21] Lubotzky, A.; Meshulam, R., A Moore bound for simplicial complexes, Bulletin of the London Mathematical Society, 39, 353-358, (2007) · Zbl 1180.13028
[22] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277, (1988) · Zbl 0661.05035
[23] Lubotzky, A.; Samuels, B.; Vishne, U., Ramanujan complexes of type A˜d, Israel Journal of Mathematics, 149, 267-299, (2005) · Zbl 1087.05036
[24] Lubotzky, A.; Samuels, B.; Vishne, U., Explicit constructions of Ramanujan complexes of type A˜d, European Journal of Combinatorics, 26, 965-993, (2005) · Zbl 1135.05038
[25] A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Progress in Mathematics, Vol. 125, Birkhäuser Verlag, Basel, 1994. · Zbl 0826.22012
[26] Lubotzky, A., Expander graphs in pure and applied mathematics, Bulletin of the American Mathematical Society, 49, 113-162, (2012) · Zbl 1232.05194
[27] Lubotzky, A., Ramanujan complexes and high dimensional expanders, Japanese Journal of Mathematics, 9, 137-169, (2014) · Zbl 1302.05095
[28] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Mathematical Monographs, Clarendon Press, Oxford University Press, New York, 1979. · Zbl 0487.20007
[29] Margulis, G. A., Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, Problemy Peredachi Informatsii, 24, 51-60, (1988) · Zbl 0708.05030
[30] Papikian, M., On eigenvalues of p-adic curvature, Manuscripta Mathematica, 127, 397-410, (2008) · Zbl 1273.20024
[31] Parzanchevski, O., Mixing in high-dimensional expanders, Combinatorics, Probability and Computing, 26, 746-761, (2017) · Zbl 1371.05329
[32] Parzanchevski, O.; Rosenthal, R., Simplicial complexes: Spectrum, homology and random walks, Random Structures & Algorithms, 50, 225-261, (2017) · Zbl 1359.05114
[33] Parzanchevski, O.; Rosenthal, R.; Tessler, R. J., Isoperimetric inequalities in simplicial complexes, Combinatorica, 36, 195-227, (2016) · Zbl 1389.05174
[34] P. Sarnak, Some Applications of Modular Forms, Cambridge Tracts in Mathematics, Vol. 99, Cambridge University Press, Cambridge, 1990. · Zbl 0721.11015
[35] Sarveniazi, A., Explicit construction of a Ramanujan (n1, n2,...,nd−1)-regular hypergraph, Duke Mathematical Journal, 139, 141-171, (2007) · Zbl 1180.11016
[36] Tadic, M., Classification of unitary representations in irreducible representations of general linear group (non-archimedean case), Annales Scientifiques de l’École Normale Supérieure, 19, 335-382, (1986) · Zbl 0614.22005
[37] Zelevinsky, A. V., Induced representations of reductive p-adic groups. II. On irreducible representations of GL(n), Annales Scientifiques de l’École Normale Supérieure, 13, 165-210, (1980) · Zbl 0441.22014
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.