On eigenvalues of random complexes

DOI10.1145/2261250.2261272zbMath1353.05079arXiv1411.4906OpenAlexW2963460671MaRDI QIDQ503252

Uli Wagner, Anna Gundert

Publication date: 11 January 2017

Published in: Israel Journal of Mathematics, Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

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=Omega(log n/n)$, the eigenvalues of these 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 higher-dimensional Laplacian spectra capture the notion of coboundary expansion - a generalization of edge expansion that arose in recent work of Linial and Meshulam and of Gromov. We show that this most straightforward version of a higher-dimensional discrete Cheeger inequality fails, in quite a strong way: For every $kgeq 2$ and $nin mathbb{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(1/sqrt{n}),1+O(1/sqrt{n})]$) but whose coboundary expansion is bounded from above by $O(log n/n)$ and so tends to zero as $n ightarrow infty$; moreover, $Y^k_n$ can be taken to have vanishing integer homology in dimension less than $k$.

Full work available at URL: https://arxiv.org/abs/1411.4906

zbMATH Keywords

eigenvaluessimplicial complexesrandom graphshypergraphsisoperimetryLaplaciansexpander graphsmeasure concentrationrandom complexes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Simplicial sets and complexes in algebraic topology (55U10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Cheeger-type inequality on simplicial complexes
• A simpler proof of the Boros-Füredi-Bárány-Pach-Gromov theorem
• On eigenvalues of random complexes
• Topology of random 2-complexes
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
• On Gromov's method of selecting heavily covered points
• Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Homological connectivity of random 2-complexes
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• Eigenvalues and expanders
• Explicit constructions of linear-sized superconcentrators
• The eigenvalues of random symmetric matrices
• On the second eigenvalue of a graph
• Counting colorful multi-dimensional trees
• Some geometric aspects of graphs and their eigenfunctions
• On the Betti numbers of chessboard complexes
• Computing Betti numbers via combinatorial Laplacians
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Collapsibility and vanishing of top homology in random simplicial complexes
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• The threshold for integer homology in random \(d\)-complexes
• The spectral gap of random graphs with given expected degrees
• Isoperimetric inequalities in simplicial complexes
• Spectra of combinatorial Laplace operators on simplicial complexes
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• Eigenvalues and homology of flag complexes and vector representations of graphs
• Harmonic functions and boundary value problems on a chain complex
• Higher dimensional discrete Cheeger inequalities
• The threshold function for vanishing of the top homology group of random 𝑑-complexes
• The fundamental group of random 2-complexes
• Loose laplacian spectra of random hypergraphs
• Overlap properties of geometric expanders
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
• Spectral Gaps of Random Graphs and Applications
• Expander graphs and their applications
• An Elementary Construction of Constant-Degree Expanders
• Homological connectivity of random k -dimensional complexes
• Simplicial matrix-tree theorems
• Matrix Analysis
• Finite-Difference Approach to the Hodge Theory of Harmonic Forms
• The Spectra of Random Graphs with Given Expected Degrees
• Combinatorial Laplacians of matroid complexes
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• COBOUNDARY EXPANDERS
• Spectral techniques applied to sparse random graphs
• Minors in random and expanding hypergraphs
• On the Laplacian Eigenvalues of G_n,p
• Combinatorial Laplacian of the matching complex

Related Items (33)

Random Simplicial Complexes: Models and Phenomena ⋮ Isoperimetric inequalities in simplicial complexes ⋮ Maps on random hypergraphs and random simplicial complexes ⋮ On the spectrum of dense random geometric graphs ⋮ A Cheeger-Buser-type inequality on CW complexes ⋮ Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes ⋮ A Cheeger-type inequality on simplicial complexes ⋮ Algebraic and combinatorial expansion in random simplicial complexes ⋮ Random hypergraphs, random simplicial complexes and their Künneth-type formulae ⋮ Continuum limit for a discrete Hodge-Dirac operator on square lattices ⋮ Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian ⋮ Bounded degree cosystolic expanders of every dimension ⋮ Unnamed Item ⋮ Mixing in High-Dimensional Expanders ⋮ Local spectral expansion approach to high dimensional expanders. II: Mixing and geometrical overlapping ⋮ Simplicial complexes: Spectrum, homology and random walks ⋮ Spectral expansion of random sum complexes ⋮ Ramanujan complexes and high dimensional expanders ⋮ Thresholds for vanishing of `isolated' faces in random Čech and Vietoris-Rips complexes ⋮ Random Latin squares and 2-dimensional expanders ⋮ Expansion of random graphs: new proofs, new results ⋮ Simplex links in determinantal hypertrees ⋮ On eigenvalues of random complexes ⋮ High order random walks: beyond spectral gap ⋮ Spectral gaps, missing faces and minimal degrees ⋮ Simplicial Kirchhoff index of random complexes ⋮ Simplicial branching random walks ⋮ On eigenvalue problems for the random walks on the Sierpinski pre- gaskets ⋮ STABILITY, COHOMOLOGY VANISHING, AND NONAPPROXIMABLE GROUPS ⋮ On simple connectivity of random 2-complexes ⋮ The theta number of simplicial complexes ⋮ High Dimensional Random Walks and Colorful Expansion ⋮ Random Steiner systems and bounded degree coboundary expanders of every dimension

This page was built for publication: On eigenvalues of random complexes