7
$\begingroup$

I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is:

  • Could someone point me to a reference that discusses both of these notions? (I've found various lecture notes on related topics but these seem to focus either on expansion or on conductance...)

I've read that the expansion of $G$ is a measure for the speed of mixing of a random walk on $G$, i.e., the time for getting close to the stationary distribution. For a $d$-regular graph with constant expansion, for example, the mixing time is $\Theta(\log n)$. The same seems to be true for the conductance $\Phi(G)$, i.e., if $\Phi(G)$ is constant, then a random walk on $G$ will also mix in $\Theta(\log n)$ time. Moreover, this property of conductance holds even in non-regular graphs, and, for $d$-regular graphs the expansion of $G$ can be found by simply dividing the conductance of $G$ by $d$. This begs the following question:

  • Why should we consider the expansion of a graph $G$, when the conductance seems to be a stronger measure (that subsumes expansion)?
$\endgroup$
4
$\begingroup$

There are several different definitions for the expansion of a graph, but all of them are spatial. One common definition defined the expansion $h(G)$ of a graph $G$ as $$ h(G) = \min_{|S| \leq |G|/2} \frac{|\partial S|}{|S|}, $$ where $S$ is a set of vertices containing at most half of the vertices, and $\partial S$ is the (edge) boundary of $S$, the number of edges connecting $S$ to $\overline{S}$. For a $d$-regular connected graph, there is a strong connection between $h(G)$ and a spectral parameter, the eigenvalue gap $\lambda(G)$, which is the smallest non-zero eigenvalue of the Laplacian. For a $d$-regular connected graph, Cheeger's inequality states that $$ \frac{\lambda(G)}{2} \leq h(G) \leq \sqrt{2d\lambda(G)}. $$ This is often put in terms of the second largest eigenvalue $\lambda_2(G)$ of the adjacency matrix of $G$, which satisfies $\lambda_2(G) = d - \lambda(G)$. There must be versions of Cheeger's inequality for non-regular graphs, and I'll let you look them up.

A lot of information on expander graphs can be found in the survey (based on course notes) Expander graphs and their applications by Hoori, Linial and Wigderson. Other information is scattered among lecture notes and even recent papers.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.