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

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

2006-06-07

arxiv.org/abs/math/0606167v2

Electronic Communications in Probability, vol. 12, pp. 377-389, 2007.

Mathematics

Probability

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sharp edge, vertex, and mixed Cheeger type inequalities for finite Markov kernels does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp edge, vertex, and mixed Cheeger type inequalities for finite Markov kernels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp edge, vertex, and mixed Cheeger type inequalities for finite Markov kernels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-698447