11
$\begingroup$

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 inequality for 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.

$\endgroup$
  • 1
    $\begingroup$ That's an interesting way to generalize Cheeger. My feeling is that it will help to first look at the irreducible aperiodic case, so that you have a unique maximum (in absolute value) real simple eigenvalue, and corresponding eigenvector is real and positive (by Perron-Frobenius). $\endgroup$ – Sasho Nikolov Jul 21 '12 at 17:46
  • 1
    $\begingroup$ I believe I am looking at that case: (i) irreducible - $G$ is assumed to be strongly connected (ii) aperiodic - $P$ is defined to have $P_{ii} \geq 1/2$; this was precisely so as not to deal with periodicity issues. $\endgroup$ – robinson Jul 21 '12 at 17:57
  • $\begingroup$ I missed the strongly connected part. Cool. $\endgroup$ – Sasho Nikolov Jul 21 '12 at 18:03
  • $\begingroup$ Have you elaborated on your ideas? I would be very interested to hear about further developments. $\endgroup$ – Delio M. Mar 11 '15 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.