# Expansion in strongly regular graphs

Have you seen the following statement proven anywhere?

Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ vertices in $G$ such that the neighborhood of $A$ is of size less than $3n/4$.

A vertex in $A$ in this case would be included in the neighborhood of $A$ iff it is adjacent to another vertex in $A$. It seems like this should be known, if it's true.

• For the specific parameters you give, it seems like the rook graph (vertices are an $n \times n$ grid of points, two vertices adjacent if they're in the same row or column) is a counterexample, with $A$ as any $n/2 \times n/2$ subgrid. But this doesn't rule out an example with slightly smaller expansion. Nov 4, 2015 at 20:44
• You're right, I made a mistake - in fact I should have written "the neighborhood of $A$ is LESS than $3n/4$". Edited now. Good catch!
– EJI
Nov 4, 2015 at 20:54

Consider the complete tripartite graph $G = \langle X\cup Y\cup Z,E\rangle$ with $|X|=|Y|=|Z|=\frac{n}{3}$, and $E = X\times Y\cup X\times Z \cup Y\times Z$. This graph is strongly (n,2n/3,n/3,2n/3)-regular, and e.g. $X$ has more than $\frac{n}{4}$ vertices and less than $\frac{3}{4}n$ neighbors, so this is a counterexample to your conjecture.
Question: What is the minimal $\alpha>0$ such that in every strongly regular graph, every set $S \subseteq V$ whose size is at least $\alpha n$ has at least $(1-\alpha) n$ neighbors, and which strongly regular graph achieves this $\alpha$?
This seems like a natural question, but I wouldn't be surprised if no one had considered it. It looks like a good research question to me. My example implies $\alpha \geq 1/3$.