14
$\begingroup$

Given an undirected, regular graph $G=(V,E)$, what is the relationship between its diameter - defined as the largest distance between two nodes - and its conductance, defined as $$\min_{S \subset V} ~\frac{e(S,S^c)}{\min(|S|,|S^c|)},$$ where $e(S,S^c)$ is the number of edges crossing between $S$ and $S^c$.

More concretely suppose I know the diameter is at least (or at most) $D$. What does this tell me about the conductance, if anything? And, conversely, suppose I know the conductance is at most (or at least) $\alpha$. What does this tell me about the diameter, if anything?

$\endgroup$
4
  • 2
    $\begingroup$ It looks like the property you're asking is the graph expansion instead of graph conductance, which is defined as $\min_{S \subseteq V} \ {e(S,\overline{S})}/{\min\{\mathsf{vol}(S), \mathsf{vol}(\overline{S})\}}$, where $\mathsf{vol}(S)$ is defined as $\sum_{v \in S} \deg(v)$. Which one is the property you want?? $\endgroup$ Jul 1, 2011 at 10:30
  • 2
    $\begingroup$ @Hsien-Chi Chang - since the graph is regular, I believe conductance and expansion should be the same up to a multiplicative factor of the degree $d$. $\endgroup$
    – robinson
    Jul 1, 2011 at 16:43
  • 1
    $\begingroup$ Ah, I did not notice that the graph is regular. Thanks for the explanation. $\endgroup$ Jul 1, 2011 at 16:59
  • $\begingroup$ @Hsien-ChihChang張顯之: I thought graph expansion and graph conductance are the same concept. Do you have references on the definition in your comment? $\endgroup$
    – Tim
    Dec 28, 2012 at 18:11

1 Answer 1

13
$\begingroup$

As Hsieh notes, your definition of conductance is off from the one I know by a factor of $d$, where $d$ is the degree of the regular graph. This is also known as edge expansion for regular graphs.

A relationship between edge expansion and diameter is quite easy to show. Intuitively, an expander is "like" a complete graph, so all vertices are "close" to each other. More formally, let

$$ \min_{S \subseteq V}\ { \frac{ e(S, S^c) }{ d \cdot \min\{|S|, |S^c|\} }} \geq \alpha $$

Take any set of vertices $S$ with $|S| \leq |V|/2$. There are at least $\alpha d |S|$ edges coming out of $S$ and since $G$ is $d$-regular, the neighborhood of $S$ (including $S$ itself) is of size at least $(1+\alpha)|S|$. Applying this claim inductively, starting from $S = \{u\}$ for any vertex $u$, we see that for some $t = O(\log_{1 + \alpha } |V|)$, $u$'s $t$-hop neighborhood has size at least $|V|/2$. Therefore, the $t+1$-hop neighborhood of any vertex $v$ has to intersect the $t$-hop neighborhood of $u$, or the graph would have more than $|V|$ vertices, a contradiction. So you have

$$ D = O\left(\frac{\log |V|}{\log (1 + \alpha)}\right) $$

Of course, it also follows that having a lower bound on the diameter implies an upper bound on edge expansion.

I don't think small diameter implies conductance. If you don't insist on regular graphs (and use Hsieh's definition), then two complete graphs connected by a single edge provides a counterexample.

$\endgroup$
4
  • $\begingroup$ I'm about to post an answer and now I don't have to, I can simply upvote yours instead ;) Thanks for the good answer! $\endgroup$ Jul 1, 2011 at 17:15
  • $\begingroup$ I hope the total time you and I spent away from research was minimized :) $\endgroup$ Jul 1, 2011 at 19:25
  • 1
    $\begingroup$ @robinson: this simple fact and rapid mixing are the basis of many (most?) applications of expander families of regular graphs. the small diameter property for example is the basis of the application to solving st connectivity in logspace $\endgroup$ Jul 1, 2011 at 19:27
  • 1
    $\begingroup$ my original answer had a bug: the argument I had written was for vertex expansion, but we're working with edge expansion here. i've fixed the bug, and the bound now is slightly worse $\endgroup$ Nov 6, 2012 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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