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

Simple item page
dc.creatorMontenegro, Ravi
dc.date2006-06-07
dc.date2007-05-05
dc.date.accessioned2026-07-07T08:46:34Z
dc.date.available2026-07-07T08:46:34Z
dc.descriptionWe 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.
dc.descriptionv1: original version (>20 pages) v2: v1 was far too verbose; this pares it to under 10 pages
dc.identifierhttps://arxiv.org/abs/math/0606167
dc.identifierhttp://arxiv.org/abs/math/0606167
dc.identifierElectronic Communications in Probability, vol. 12, pp. 377-389, 2007.
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/143293
dc.subjectProbability
dc.subjectCombinatorics
dc.subject60J10
dc.titleSharp edge, vertex, and mixed Cheeger type inequalities for finite Markov kernels
dc.typetext

Files

Collections

arXiv