Walking on the Edge and Cosystolic Expansion

arXiv1606.01844MaRDI QIDQ6274342FDOQ6274342

Authors: Tali Kaufman, David Mass 

Publication date: 6 June 2016

Abstract: Random walks on regular bounded degree expander graphs have numerous applications. A key property of these walks is that they converge rapidly to the uniform distribution on the vertices. The recent study of expansion of high dimensional simplicial complexes, which are the high dimensional analogues of graphs, calls for the natural generalization of random walks to higher dimensions. In particular, a high order random walk on a $2$-dimensional simplicial complex moves at random between neighboring edges of the complex, where two edges are considered neighbors if they share a common triangle. We show that if a regular $2$-dimensional simplicial complex is a cosystolic expander and the underlying graph of the complex has a spectral gap larger than $1/2$, then the random walk on the edges of the complex converges rapidly to the uniform distribution on the edges.

This page was built for publication: Walking on the Edge and Cosystolic Expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6274342)