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



A question about expander graphs
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}$.


