Journal
ANNALS OF COMBINATORICS
Volume 9, Issue 1, Pages 1-19Publisher
BIRKHAUSER VERLAG AG
DOI: 10.1007/s00026-005-0237-z
Keywords
eigenvalues; Laplacian; circulation; the Cheeger inequality; random walks; Markov chains; comparison theorems
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available