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$
  • 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$ – Hsien-Chih Chang 張顯之 Jul 1 '11 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 '11 at 16:43
  • 1
    $\begingroup$ Ah, I did not notice that the graph is regular. Thanks for the explanation. $\endgroup$ – Hsien-Chih Chang 張顯之 Jul 1 '11 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 '12 at 18:11
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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Hsien-Chih Chang 張顯之 Jul 1 '11 at 17:15
  • $\begingroup$ I hope the total time you and I spent away from research was minimized :) $\endgroup$ – Sasho Nikolov Jul 1 '11 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$ – Sasho Nikolov Jul 1 '11 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$ – Sasho Nikolov Nov 6 '12 at 17:06

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.