Pergunta

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)?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top