9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Kevin P. Costello Nov 4 '15 at 20:44
  • $\begingroup$ 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! $\endgroup$ – EJI Nov 4 '15 at 20:54
5
$\begingroup$

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.

On the other hand, since the spectrum of strongly regular graphs is known precisely (see https://en.wikipedia.org/wiki/Strongly_regular_graph#Eigenvalues), one can get bounds on the edge expansion of such a graph via Cheeger's inequality, which implies results like the one you 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$.

| cite | improve this answer | |
$\endgroup$

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.