Premium
Algebraic and combinatorial expansion in random simplicial complexes
Author(s) -
Fountoulakis Nikolaos,
Przykucki Michał
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21036
Subject(s) - mathematics , spectral gap , algebraic connectivity , simplicial complex , combinatorics , random walk , logarithm , bounded function , constant (computer programming) , conductance , laplace transform , random graph , operator (biology) , discrete mathematics , graph , laplacian matrix , mathematical analysis , biochemistry , statistics , chemistry , repressor , computer science , transcription factor , gene , programming language
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 ( d − 1 ) ‐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.