Algebraic and combinatorial expansion in random simplicial complexes

Research output: Contribution to journalArticlepeer-review

Colleges, School and Institutes

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 (Combinatorica 36, 2016). 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 generalises 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.

Details

Original languageEnglish
JournalRandom Structures and Algorithms
Early online date16 Jul 2021
Publication statusE-pub ahead of print - 16 Jul 2021

Keywords

  • Cheeger constant, conductance, Laplace operator, random simplicial complexes