×

zbMATH — the first resource for mathematics

Simplicial complexes: spectrum, homology and random walks. (English) Zbl 1359.05114
Summary: 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 H. Kesten’s result [Trans. Am. Math. Soc. 92, 336–354 (1959; Zbl 0092.33503)] 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.

MSC:
05C81 Random walks on graphs
05E45 Combinatorial aspects of simplicial complexes
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Citations:
Zbl 0092.33503
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Alon, Eigenvalues and expanders, Combinatorica 6 pp 83– (1986) · Zbl 0661.05053
[2] Alon, {\(\lambda\)}1, isoperimetric inequalities for graphs, and superconcentrators, J Combin Theory Ser B 38 pp 73– (1985) · Zbl 0549.05051
[3] Dotterrer, Coboundary expanders, J Topol Anal 4 pp 499– (2012) · Zbl 1259.05151
[4] Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Tran Am Math Soc 284 pp 787– (1984) · Zbl 0512.39001
[5] P. G. Doyle J. L. Snell Random walks and electric networks, no. 22, Mathematical Association of America 1984 174 · Zbl 0583.60065
[6] Eckmann, Harmonische funktionen und randwertaufgaben in einem komplex, Commentarii Math Helvetici 17 pp 240– (1944) · Zbl 0061.41106
[7] Feller, An introduction to probability theory II (1966) · Zbl 0138.10207
[8] Fox, Overlap properties of geometric expanders, J Reine Angew Math 671 pp 49– (2012)
[9] Garland, p-Adic curvature and the cohomology of discrete subgroups of p-adic groups, Ann Math 97 pp 375– (1973) · Zbl 0262.22010
[10] K. Golubev O. Parzanchevski Spectrum and combinatorics of Ramanujan triangle complexes 2014 27
[11] Gromov, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geomet Funct Anal 20 pp 416– (2010) · Zbl 1251.05039
[12] A. Gundert M. Szedlák Higher dimensional Cheeger inequalities, In Annual Symposium on Computational Geometry (New York, NY, USA) 2014 181:181 181:188 · Zbl 1395.05100
[13] A. Gundert On expansion and spectral properties of simplicial complexes 2013
[14] A. Gundert U. Wagner On Laplacians of random complexes 2012 151 160 · Zbl 1293.05210
[15] Grigorchuk, On the asymptotic spectrum of random walks on infinite families of graphs, Random walks and discrete potential theory (Cortona, 1997), Sympos Math 39 pp 188– (1999)
[16] Horak, Spectra of combinatorial Laplace operators on simplicial complexes, Adv Math 244 pp 303– (2013) · Zbl 1290.05103
[17] Kesten, Symmetric random walks on groups, Trans Am Math Soc 92 pp 336– (1959) · Zbl 0092.33503
[18] Li, Ramanujan hypergraphs, Geom Funct Anal 14 pp 380– (2004) · Zbl 1084.05047
[19] Linial, Homological connectivity of random 2-complexes, Combinatorica 26 pp 475– (2006) · Zbl 1121.55013
[20] Lyons, Probability on trees and networks (2005)
[21] Lubotzky, Ramanujan complexes of type Ad, Israel J Math 149 pp 267– (2005) · Zbl 1087.05036
[22] Lubotzky, Ramanujan complexes and high dimensional expanders, Japanese J Math 9 pp 137– (2014) · Zbl 1302.05095
[23] Lyons, A simple criterion for transience of a reversible Markov chain, Ann Probab 11 pp 393– (1983) · Zbl 0509.60067
[24] Munkres, Elements of algebraic topology (1984)
[25] Meshulam, Homological connectivity of random k-dimensional complexes, Random Struct Algorithms 34 pp 408– (2009) · Zbl 1177.55011
[26] Matoušek, On Gromov’s method of selecting heavily covered points, Discrete Comput Geom 52 pp 1– (2014) · Zbl 1298.51027
[27] Nilli, On the second eigenvalue of a graph, Discrete Math 91 pp 207– (1991) · Zbl 0771.05064
[28] O. Parzanchevski Mixing in high-dimensional expanders 2013 12
[29] Parzanchevski, Isoperimetric inequalities in simplicial complexes, Combinatorica pp 1– (2015) · Zbl 1389.05174
[30] Steenbergen, A Cheeger-type inequality on simplicial complexes, Adv App Math 56 pp 56– (2014) · Zbl 1305.55010
[31] Tanner, Explicit concentrators from generalized n-gons, SIAM J Algebraic Discrete Methods 5 pp 287– (1984) · Zbl 0554.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.