Videos

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