Simplicial complexes: Spectrum, homology and random walks1. Issue 2 (3rd May 2016)

• Record Type: Journal Article
• Authors: Parzanchevski, Ori; Rosenthal, Ron
• Is Part Of: Random structures & algorithms. Volume 50:Issue 2(2017)
• Page Start: 225
• Page End: 261
• Publication Date: 2016-05-03
• Subjects: random walk -- simplicial complexes -- spectrum -- homology; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20657
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: This paper studies the dynamical and asymptotic aspects of high‐dimensional expanders. We define a stochastic process on simplicial complexes of arbitrary dimension, which detects the existence of homology in the same way that a random walk on a finite graph reflects its connectedness. Through this, we obtain high‐dimensional analogues of graph properties such as bipartiteness, return probability, amenability and transience/recurrence. In the second part of the paper we generalize Kesten's result on the spectrum of regular trees, and of the connection between return probabilities and spectral radius. We study the analogue of the Alon‐Boppana theorem on spectral gaps, and exhibit a counterexample for its high‐dimensional counterpart. We show, however, that under some assumptions the theorem does hold ‐ for example, if the codimension‐one skeletons of the complexes in question form a family of expanders. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 225–261, 2017