Sharp edge, vertex, and mixed Cheeger type inequalities for finite Markov kernels

Abstract

We show how the evolving set methodology of Morris and Peres can be used to show Cheeger inequalities for bounding the spectral gap of a finite Markov kernel. This leads to sharp versions of several previous Cheeger inequalities, including ones involving edge-expansion, vertex-expansion, and mixtures of both. A bound on the smallest eigenvalue also follows.

v1: original version (>20 pages) v2: v1 was far too verbose; this pares it to under 10 pages