Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\mathcal G=(G_n)_n$ be a family of expanders; i.e. each $G_n=(V_n,E_n)$ is a finite connected d-regular graph of order say $\alpha(n)$, with $\alpha(n)\to\infty$, and each isoperimetric constant $\iota_n$ is bounded below by some positive real number $\epsilon$.

Let me suppose that $\alpha(n)=2n$, just to keep notation simpler. Let $A\subseteq V_n$ containing $n+1$ vertices. Denote by $M(A)$ the maximal distance of a vertex of $V_n$ from $A$.

Question: Can we found a uniform bound $M(A)\leq K$?

Here uniform means that $K$ may depend on the regularity $d$, on $\epsilon$, on other stuff, but neither on $A$ nor on $n$.

My intuition, maybe wrong, is that expanders have strong connectivity properties and therefore, taking $n+1$ vertex, the remaining $n-1$ cannot stay too far away.

Thank you in advance,

Valerio

share|improve this question
    
The obvious bound is logarithmic in $n,$ I doubt you can get it down to a constant. –  Igor Rivin Mar 14 '12 at 15:02

1 Answer 1

up vote 9 down vote accepted

A uniform bound is too much to ask: expanders have logarithmic diameter.

For a counterexample, the Cayley graphs of $\text{SL}_3(\mathbf{Z}/m)$, with respect to the generating set

$$E_{ij}(\pm1)\qquad (i\neq j)$$

(i.e. $1$s on the diagonal, one other $\pm1$ entry, zeros elsewhere) are known to be expanders. A product of $k$ of these elements $E_{ij}(\pm1)$ will be a matrix whose entries are bounded in absolute value by $2^k$ (I believe). Thus, provided that $m>2^{k+1}$, these generators do not generate half the group in constant time.

EDIT: I think something much stronger is true. Namely, every nontrivial expander family is a counterexample. Suppose that your proposed bound $M(A)\leq K$ holds for a $d$-regular graph $G$. Starting with a vertex $v$, let $A$ be the set of vertices within a distance $K$ of $v$. Since $M(G\backslash A)>K$, we must have $|A|\geq |G|/2$. Then your bound implies $M(A)\leq K$. Hence every vertex in $G$ is within a distance $2K$ of $v$. In particular, $|G|\leq d^{2K}$.

share|improve this answer
1  
I'm visualizing this backwards to the way it is proposed. Namely, if you don't generate half the group, take your set to be some $n+1$ of the elements you didn't reach. –  Sean Eberhard Mar 14 '12 at 15:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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