Walking on the Edge and Cosystolic Expansion

Understand

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.