A question about expander graphs

Question

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

Answer 1

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