Cheeger Inequalities and Random Walks on Simplicial Complexes
Presenter
April 28, 2014
Keywords:
- Simplicial Complex, Combinational
MSC:
- 05E45
Abstract
We state some results on Cheeger Inequalities for the combinatorial
Laplacian and random walks on simplicial complexes.
Specifically, for the combinatorial Laplacian we prove that a Cheeger
type inequality holds on the highest dimension, or for the boundary
operator with Dirichlet boundary conditions. We also show that
coboundary expanders do not satisfy natural Buser or Cheeger
inequalities. We provide some statements about middle dimensions.
We also introduce random walks with absorbing states on simplicial
complexes. Given a simplicial complex of dimension d, a random walk
with an absorbing state is defined which relates to the spectrum of
the k-dimensional Laplacian. We also examine an application of random
walks on simplicial complexes to a semi-supervised learning problem.
Specifically, we consider a label propagation algorithm on oriented
edges, which applies to a generalization of the partially labelled
classification problem on graphs.
Joint work with: John Steenbergen, Caroline Klivans, Anil Hirani, and
Mark Schubel