Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics 72 (1988), 15–19.
N. Alon and V. D. Milman, λ1, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory. Series B 38 (1985), 73–88.
A. Borel, Admissible representations of a semi-simple group over a local field with vectors fixed under an Iwahori subgroup, Inventiones Mathematicae 35 (1976), 233–259.
W. Casselman, On a p-adic vanishing theorem of Garland, Bulletin of the American Mathematical Society 80 (1974), 1001–1004.
W. Casselman, The unramified principal series of p-adic groups. I. The spherical function, Compositio Mathematica 40 (1980), 387–406.
M. Cowling, U. Haagerup and R. Howe, Almost L 2 matrix coefficients, Journal für die Reine und Angewandte Mathematik 387 (1988), 97–110.
D. I. Cartwright and T. Steger, Elementary symmetric polynomials in numbers of modulus 1, Canadian Journal of Mathematics 54 (2002), 239–262.
D. I. Cartwright, P. Solé and A. Żuk, Ramanujan geometries of type A˜n, Discrete Mathematics 269 (2003), 35–43.
B. Eckmann, Harmonische funktionen und randwertaufgaben in einem komplex, Commentarii Mathematici Helvetici 17 (1944), 240–255.
S. Evra, K. Golubev and A. Lubotzky, Mixing properties and the chromatic number of Ramanujan complexes, International Mathematics Research Notices 22 (2015), 11520–11548.
J. Fox, M. Gromov, V. Lafforgue, A. Naor and J. Pach, Overlap properties of geometric expanders, Journal für die Reine und Angewandte Mathematik 671 (2012), 49–83.
U. A. First, The Ramanujan property for simplicial complexes, preprint, arXiv:1605.02664.
J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), 71–76.
H. Garland, p-adic curvature and the cohomology of discrete subgroups of p-adic groups, Annals of Mathematics 97 (1973), 375–423.
A. Gundert and M. Szedlák, Higher dimensional Cheeger inequalities, in Computational Geometry SoCG’14, ACM, New York, 2014, pp. 181–188.
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.
S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society 43 (2006), 439–562.
A. J. Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), Academic Press, New York, 1970, pp. 79–91.
M. H. Kang, W. C.W. Li and C. J. Wang, The zeta functions of complexes from PGL(3): a representation-theoretic approach, Israel Journal of Mathematics 177 (2010), 335–348.
W. C. W. Li, Ramanujan hypergraphs, Geometric and Functional Analysis 14 (2004), 380–399.
A. Lubotzky and R. Meshulam, A Moore bound for simplicial complexes, Bulletin of the London Mathematical Society 39 (2007), 353–358.
A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.
A. Lubotzky, B. Samuels and U. Vishne, Ramanujan complexes of type A˜d, Israel Journal of Mathematics 149 (2005), 267–299.
A. Lubotzky, B. Samuels and U. Vishne, Explicit constructions of Ramanujan complexes of type A˜d, European Journal of Combinatorics 26 (2005), 965–993.
A. Lubotzky, Discrete Groups, Expanding Graphs and Invariant Measures, Progress in Mathematics, Vol. 125, Birkhäuser Verlag, Basel, 1994.
A. Lubotzky, Expander graphs in pure and applied mathematics, Bulletin of the American Mathematical Society 49 (2012), 113–162.
A. Lubotzky, Ramanujan complexes and high dimensional expanders, Japanese Journal of Mathematics 9 (2014), 137–169.
I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Mathematical Monographs, Clarendon Press, Oxford University Press, New York, 1979.
G. A. Margulis, Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, Problemy Peredachi Informatsii 24 (1988), 51–60.
M. Papikian, On eigenvalues of p-adic curvature, Manuscripta Mathematica 127 (2008), 397–410.
O. Parzanchevski, Mixing in high-dimensional expanders, Combinatorics, Probability and Computing 26 (2017), 746–761.
O. Parzanchevski and R. Rosenthal, Simplicial complexes: Spectrum, homology and random walks, Random Structures & Algorithms 50 (2017), 225–261.
O. Parzanchevski, R. Rosenthal and R. J. Tessler, Isoperimetric inequalities in simplicial complexes, Combinatorica 36 (2016), 195–227.
P. Sarnak, Some Applications of Modular Forms, Cambridge Tracts in Mathematics, Vol. 99, Cambridge University Press, Cambridge, 1990.
A. Sarveniazi, Explicit construction of a Ramanujan (n1, n2,...,nd−1)-regular hypergraph, Duke Mathematical Journal 139 (2007), 141–171.
M. Tadic, Classification of unitary representations in irreducible representations of general linear group (non-archimedean case), Annales Scientifiques de l’École Normale Supérieure 19 (1986), 335–382.
A. V. Zelevinsky, Induced representations of reductive p-adic groups. II. On irreducible representations of GL(n), Annales Scientifiques de l’École Normale Supérieure 13 (1980), 165–210.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Golubev, K., Parzanchevski, O. Spectrum and combinatorics of two-dimensional Ramanujan complexes. Isr. J. Math. 230, 583–612 (2019). https://doi.org/10.1007/s11856-019-1828-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-019-1828-z