<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume9 Issue1" %>
Laplacians and the Cheeger Inequality for Directed Graphs
Fan Chung
University of California, San Diego, La Jolla, CA 92093-0112, USA
fan@ucsd.edu
Annals of Combinatorics 9 (1) p.1-19 March, 2005
AMS Subject Classification: 05C20, 05C50, 15A42, 60J05
Abstract:
We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.
Keywords: eigenvalues, Laplacian, circulation, the Cheeger inequality, random walks, Markov chains, comparison theorems

References:

1. D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs, draft of a book.

2. N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986) 86--96.

3. C. Asci, Generating uniform random vectors, J. Theoret. Probab. 14 (2001) 333--356.

4. F. Bassiri, Random walks on finite groups of multiplicity two, Ph. D. Thesis, Harvard University, 1997.

5. A. Björner and L. Lovász, Chip-firing games on directed graphs, J. Algebraic Combin. 1 (1992) 305-328.

6. F. Chung, Spectral Graph Theory, AMS Publications, 1997.

7. P. Diaconis and D.W. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab. 1 (1991) 36--61.

8. P. Diaconis and L. Saloff-Coste, Comparison theorems for reversible Markov chains, Ann. Appl. Probab. 3 (1993) 696--730.

9. R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1990.

10. J.A. Fill, Eigenvalue bounds on convergence to stationarity for non-reversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab. 1 (1991) 62--87.

11. M. Hildebrand, Rates of convergence for a non-reversible Markov chain sampler, preprint.