Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to directed graphs. I state a possible generalization of Cheeger's inequality next. I am asking first about its correctness and secondly about whether any results along these lines are known or possible. Let $G=(V,E)$ be a strongly connected directed graph. Consider the lazy random walk on $G$: this is the Markov chain whose transition probability matrix is $P_{ii} = 1/2$, $P_{ij}=1/d(i)$ if $(i,j) \in E$, where $d(i)$ is the out-degree of node $i$, and $P_{ij}=0$ otherwise. Let $\pi$ be the unique left eigenvector corresponding to the eigenvalue $1$. Naturally, define $\pi(S) = \sum_{i \in S} \pi(i)$. Then the Cheeger constant of $P$ may be defined as  $$ h(P) = \min_{S \subset V} \frac{\sum_{i \in S, j \in S^c} \pi(i) P_{ij}}{\pi(S) \pi(S^c)}$$Now if $G$ is undirected, the part of Cheeger's inequality I am interested in says that$$ 1 - \lambda_1 \geq \Omega(h(P)^2)$$ where $\lambda_1$ is the largest eigenvalue of $P$ not equal to $1$. In the directed case, the eigenvalues are no longer real. Nevertheless, one can define $\lambda$ to be the largest absolute value of any eigenvalue of $P$ not equal to $1$. Then, is it true that $$ 1 - \lambda \geq \Omega (h(P)^2)$$ Alternatively, is any sort of result along these lines possible, perhaps with different definition of Cheeger constant? The only reference I was able to find was Laplacians and the Cheeger inequalityfor directed graphs, F. Chung, Annals of Combinatorics, 2005 (see also these lecture notes). However, the main results of that paper appear to be different than what I'm asking about. In particular, this paper seems to prove a form of Cheeger's inequality for a certain symmetric matrix, though the symmetric matrix is derived from a directed graph.
Cheeger's inequality for directed graphs?
graph theory;co.combinatorics;pr.probability;markov chains;random walks