Algebraic and combinatorial expansion in random simplicial complexes
Open Access
- 16 July 2021
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 60 (3) , 339-366
Abstract
In this paper we consider the expansion properties and the spectrum of the combinatorial Laplace operator of a d‐dimensional Linial–Meshulam random simplicial complex, above the cohomological connectivity threshold. We consider the spectral gap of the Laplace operator and the Cheeger constant as this was introduced by Parzanchevski, Rosenthal, and Tessler. We show that with high probability the spectral gap of the random simplicial complex as well as the Cheeger constant are both concentrated around the minimum co‐degree of among all ‐faces. Furthermore, we consider a random walk on such a complex, which generalizes the standard random walk on a graph. We show that the associated conductance is with high probability bounded away from 0, resulting in a bound on the mixing time that is logarithmic in the number of vertices of the complex.Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council (EP/P026729/1)
This publication has 35 references indexed in Scilit:
- Homological connectivity of random k‐dimensional complexesRandom Structures & Algorithms, 2008
- The evolution of the mixing rate of a simple random walk on the giant component of a random graphRandom Structures & Algorithms, 2008
- Homological Connectivity Of Random 2-ComplexesCombinatorica, 2006
- Spectral techniques applied to sparse random graphsRandom Structures & Algorithms, 2005
- The Spectra of Random Graphs with Given Expected DegreesInternet Mathematics, 2004
- Explicit construction of linear sized tolerant networksDiscrete Mathematics, 1988
- Difference equations, isoperimetric inequality and transience of certain random walksTransactions of the American Mathematical Society, 1984
- p-Adic Curvature and the Cohomology of Discrete Subgroups of p-Adic GroupsAnnals of Mathematics, 1973
- Random GraphsThe Annals of Mathematical Statistics, 1959
- Harmonische Funktionen und Randwertaufgaben in einem KomplexCommentarii Mathematici Helvetici, 1944