Abstract
We consider higher-dimensional generalizations of the normalized Laplacian and the adjacency matrix of graphs and study their eigenvalues for the Linial–Meshulam model X k(n, p) of random k-dimensional simplicial complexes on n vertices. We show that for p = Ω(logn/n), the eigenvalues of each of the matrices are a.a.s. concentrated around two values. The main tool, which goes back to the work of Garland, are arguments that relate the eigenvalues of these matrices to those of graphs that arise as links of (k - 2)-dimensional faces. Garland’s result concerns the Laplacian; we develop an analogous result for the adjacency matrix.
The same arguments apply to other models of random complexes which allow for dependencies between the choices of k-dimensional simplices. In the second part of the paper, we apply this to the question of possible higher-dimensional analogues of the discrete Cheeger inequality, which in the classical case of graphs relates the eigenvalues of a graph and its edge expansion. It is very natural to ask whether this generalizes to higher dimensions and, in particular, whether the eigenvalues of the higher-dimensional Laplacian capture the notion of coboundary expansion—a higher-dimensional generalization of edge expansion that arose in recent work of Linial and Meshulam and of Gromov; this question was raised, for instance, by Dotterrer and Kahle. We show that this most straightforward version of a higher-dimensional discrete Cheeger inequality fails, in quite a strong way: For every k ≥ 2 and n ∈ N, there is a k-dimensional complex Y k n on n vertices that has strong spectral expansion properties (all nontrivial eigenvalues of the normalised k-dimensional Laplacian lie in the interval \([1 - O\left( {{1 \mathord{\left/ {\vphantom {1 {\sqrt n }}} \right. \kern-\nulldelimiterspace} {\sqrt n }}} \right),\;1 + O\left( {{1 \mathord{\left/ {\vphantom {1 {\sqrt n }}} \right. \kern-\nulldelimiterspace} {\sqrt n }}} \right)])\) but whose coboundary expansion is bounded from above by O(log n/n) and so tends to zero as n → ∞; moreover, Y k n can be taken to have vanishing integer homology in dimension less than k.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. M. Adin, Counting colorful multi-dimensional trees, Combinatorica 12 (1992), 247–260.
R. Aharoni, E. Berger and R. Meshulam, Eigenvalues and homology of flag complexes and vector representations of graphs, Geometric and Functional Analysis 15 (2005), 555–566.
N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83–96.
N. Alon and V. D. Milman, λ1, Isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory. Series B 38 (1985), 73–88.
N. Alon, O. Schwartz and A. Shapira, An elementary construction of constant-degree expanders, Combinatorics, Probability and Computing 17 (2008), 319–327.
L. Aronshtam, N. Linial, T. Luczak and R. Meshulam, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete & Computational Geometry 49 (2013), 317–334.
E. Babson, C. Hoffman and M. Kahle, The fundamental group of random 2-complexes, Journal of the American Mathematical Society 24 (2011), 1–28.
A. Borel, Cohomologie des certains groupes discrets et Laplacien p-adique, in Séminaire Bourbaki, 26e année Exposé 437, Lecture Notes in Mathematics, Vol. 431, Springer, Berlin, 1973, pp. 12–35.
A. Cayley, A theorem on trees, Quarterly Journal of Pure and Applied Mathematics 23 (1889), 376–378, Collected Mathematical Papers Vol. 13, Cambridge University Press, Cambridge, 1897, pp. 26–28.
J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, in Problems in analysis (Papers dedicated to Salomon Bochner, 1969), Princeton University Press, Princeton, N J, 1970, pp. 195–199.
F. Chung, The laplacian of a hypergraph, in Expanding Graphs (Princeton, NJ, 1992), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 10, American Mathematical Society, Providence, RI, 1993, pp. 21–36.
F. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, Vol. 92, American Mathematical Society, Providence, RI, 1997.
F. Chung, L. Lu and V. Vu, The spectra of random graphs with given expected degrees, Internet Mathematics 1 (2004), 257–275.
D. Cohen, A. Costa, M. Farber and T. Kappeler, Topology of random 2-complexes, Discrete & Computational Geometry 47 (2012), 117–149.
A. Coja-Oghlan, Spectral techniques, semidefinite programs, and random graphs, Habilitationsschrift, Humboldt-Universität zu Berlin, 2005.
A. Coja-Oghlan, On the Laplacian eigenvalues of Gn,p, Combinatorics, Probability and Computing 16 (2007), 923–946.
A. Coja-Oghlan and A. Lanka, The spectral gap of random graphs with given expected degrees, Electronic Journal of Combinatorics 16 (2009), R138.
D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra, London Mathematical Society Student Texts, Vol. 75, Cambridge University Press, Cambridge, 2010.
J. Dodziuk, Finite-difference approach to the Hodge theory of harmonic forms, American Journal of Mathematics 98 (1976), 79–104.
J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Transactions of the American Mathematical Society 284 (1984), 787–794.
J. Dodziuk and V. K. Patodi, Riemannian structures and triangulations of manifolds, Journal of the Indian Mathematical Society 40 (1976), 1–52 (1977).
X. Dong and M. L. Wachs, Combinatorial Laplacian of the matching complex, Electronic Journal of Combinatorics 9 (2002), Research Paper 17, 11.
D. Dotterrer and M. Kahle, Coboundary expanders, Journal of Topology and Analysis 4 (2012), 499–514.
A. M. Duval, C. J. Klivans and J. L. Martin, Simplicial matrix-tree theorems, Transactions of the American Mathematical Society 361 (2009), 6073–6114.
B. Eckmann, Harmonische Funktionen und Randwertaufgaben in einem Komplex, Commentarii Mathematici Helvetici 17 (1945), 240–255.
U. Feige and E. Ofek, Spectral techniques applied to sparse random graphs, Random Structures Algorithms 27 (2005), 251–275.
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.
J. Friedman, J. Kahn and E. Szemerédi, On the second eigenvalue of random regular graphs, in Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, ACM, New York, 1989, pp. 587–598.
J. Friedman, Some geometric aspects of graphs and their eigenfunctions, Duke Mathematical Journal 69 (1993), 487–525.
J. Friedman, Computing Betti numbers via combinatorial Laplacians, Algorithmica 21 (1998), 331–346.
J. Friedman and P. ‘Hanlon, On the Betti numbers of chessboard complexes, Journal of Algebraic Combinatorics 8 (1998), 193–203.
Z. Füredi and J. Komlós, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), 233–241.
O. Gabber and Z. Galil, Explicit constructions of linear-sized superconcentrators, Journal of Computer and System Sciences 22 (1981), 407–420.
H. Garland, p-adic curvature and the cohomology of discrete subgroups of p-adic groups, Annals of Mathematics 97 (1973), 375–423.
W. T. Gowers, Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combinatorics, Probability and Computing 15 (2006), 143–184.
M. Gromov, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geometric and Functional Analysis 20 (2010), 416–526.
A. Gundert and M. Szedlák, Higher dimensional discrete cheeger inequalities, Journal of Computational Geometry 6 (2015), 54–71.
A. Gundert and U. Wagner, On Laplacians of random complexes, in Computational Geometry (SCG’ 12), ACM, New York, 2012, pp. 151–160.
W. V. D. Hodge, The Theory and Applications of Harmonic Integrals, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1989.
C. Hoffman, M. Kahle and E. Paquette, The threshold for integer homology in random d-complexes, preprint, arXiv:1308.6232.
C. Hoffman, M. Kahle and E. Paquette, Spectral gaps of random graphs and applications to random topology, preprint, arXiv:1201.0425.
S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society 43 (2006), 439–561 (electronic).
D. Horak and J. Jost, Spectra of combinatorial Laplace operators on simplicial complexes, Advances in Mathematics 244 (2013), 303–336.
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.
S. Janson, On concentration of probability, in Contemporary Combinatorics, Bolyai Society Mathematical Studies, Vol. 10, János Bolyai Mathematical Society, Budapest, 2002, pp. 289–301.
S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
M. Jerrum, Counting, Sampling and Integrating: Algorithms and Complexity, Lectures in Mathematics ETH Zürich, Birkhäuser, Basel, 2003.
G. Kalai, Enumeration of Q-acyclic simplicial complexes, Israel Journal of Mathematics 45 (1983), 337–351.
R. N. Karasev, A simpler proof of the Boros–Füredi–Bárány–Pach–Gromov Theorem, Discrete & Computational Geometry 47 (2012), 492–495.
G. Kirchhoff, Ueber die Auflösung der Gleichungen,auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird, Annalen der Physik 148 (1847), 497–508 (German).
W. Kook, V. Reiner and D. Stanton, Combinatorial Laplacians of matroid complexes, Journal of the American Mathematical Society 13 (2000), 129–148.
D. Kozlov, The threshold function for vanishing of the top homology group of random d-complexes, Proceedings of the American Mathematical Society 138 (2010), 4517–4527.
M. Krivelevich and B. Sudakov, Pseudo-random graphs, in More Sets, Graphs and Numbers, Bolyai Society Mathematical Studies, Vol. 15, Springer, Berlin, 2006, pp. 199–262.
D. A. Levin, Y. Peres and E. L. Wilmer, Markov Chains and Mixing Times, American Mathematical Society, Providence, RI, 2009.
N. Linial and R. Meshulam, Homological connectivity of random 2-complexes, Combinatorica 26 (2006), 475–487.
L. Lu and X. Peng, Loose Laplacian spectra of random hypergraphs, Random Structures & Algorithms 41 (2012), 521–545.
A. Lubotzky, R. S. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261–277.
A. W. Marcus, D. A. Spielman and N. Srivastava, Interlacing families I: Bipartite Ramanujan graphs of all degrees, Annals of Mathematics 182 (2015), 307–325.
A. W. Marcus, D. A. Spielman and N. Srivastava, Interlacing families IV: Bipartite Ramanujan graphs of all sizes, in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015, IEEE Computer Society, Los Alamitos, CA, 2015, pp. 1358–1377.
G. A. Margulis, Explicit constructions of expanders, Problemy Peredaci Informacii 9 (1973), 71–80.
G. A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredaci Informacii 24 (1988), 51–60.
J. MatouŠek and U. Wagner, On Gromov’s method of selecting heavily covered points, Discrete & Computational Geometry 52 (2014), 1–33.
R. Meshulam and N. Wallach, Homological connectivity of random k-dimensional complexes, Random Structures & Algorithms 34 (2009), 408–417.
I. Newman and Y. Rabinovich, On multiplicative λ-approximations and some geometric applications, in Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2012, pp. 51–67.
A. Nilli, On the second eigenvalue of a graph, Discrete Mathematics 91 (1991), 207–210.
O. Parzanchevski, R. Rosenthal and R. J. Tessler, Isoperimetric inequalities in simplicial complexes, Combinatorica 36 (2016), 195–227.
O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Annals of Mathematics 155 (2002), 157–187.
J. Steenbergen, C. Klivans and S. Mukherjee, A Cheeger-type inequality on simplicial complexes, Advances in Applied Mathematics 56 (2014), 56–77.
U. Wagner, Minors in random and expanding hypergraphs, in Computational Geometry (SCG’ 11), ACM, New York, 2011, pp. 351–360.
X.-D. Zhang, The Laplacian eigenvalues of graphs: a survey, preprint, arXiv:1111.2897v1.
A. Zuk, La propriété (T) de Kazhdan pour les groupes agissant sur les polyèdres, Comptes Rendus de l’Académie des Sciences. Série I. Mathématique 323 (1996), 453–458.
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this paper appeared at SoCG 2012. Research supported by the Swiss National Science Foundation (SNF Projects 200021-125309 and 200020-138230).
Work on this paper was conducted at the Institut für Theoretische Informatik, ETH Zürich.
Rights and permissions
About this article
Cite this article
Gundert, A., Wagner, U. On eigenvalues of random complexes. Isr. J. Math. 216, 545–582 (2016). https://doi.org/10.1007/s11856-016-1419-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-016-1419-1