Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 12 (2007) > Paper 36 open journal systems 


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

Ravi Montenegro, University of Massachusetts Lowell


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.


Full text: PDF

Pages: 377-389

Published on: October 14, 2007
Bibliography
  1. N. Alon. Eigenvalues and expanders. Combinatorica 6:2 (1986), 83--96. Math. Review 88e:05077
  2. S. Bobkov, C. Houdré and P. Tetali. &lambda&infin, vertex isoperimetry and concentration. Combinatorica 20:2 (2000), 153--172. Math. Review 2001h:05066
  3. J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Papers dedicated to Salomon Bochner) (1969), 195--199, Princeton Univ. Press, Princeton, NJ, USA. Math. Review 0402831
  4. P. Diaconis and D. Stroock. Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab 1:1 (1991), 36--61. Math. Review 92h:60103
  5. R. A. Horn and C. R. Johnson. Matrix analysis. (1985) Cambridge Univ. Press, Cambridge. Math. Review 87e:15001
  6. M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved. Proceedings of the 20th ACM Symposium on theory of computing, 1988. (1998) 235--243. Math. Review number not available.
  7. G. F. Lawler and A. D. Sokal. Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality. Trans. Amer. Math. Soc. 309:2 (1988), 557--580. Math. Review 89h:60105
  8. B. Morris and Y. Peres. Evolving sets, mixing and heat kernel bounds. Probab. Theory Related Fields 133:2 (2005), 245--266. Math. Review 2007a:60042
  9. R. Montenegro and P. Tetali. Mathematical Aspects of Mixing Times in Markov Chains. Foundations and Trends in Theoretical Computer Science 1:3 (2006), NOW Publishers, Boston-Delft.
  10. T. Stoyanov. Isoperimetric and Related Constants for Graphs and Markov Chains. (2001), Ph.D. Thesis, Department of Mathematics, Georgia Institute of Technology.
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X