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,


  • $\begingroup$ The obvious bound is logarithmic in $n,$ I doubt you can get it down to a constant. $\endgroup$
    – Igor Rivin
    Mar 14 '12 at 15:02

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}$.

  • 1
    $\begingroup$ 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. $\endgroup$ Mar 14 '12 at 15:28

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.