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$
2
  • 2
    $\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$ Commented Nov 4, 2015 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
    Commented Nov 4, 2015 at 20:54

1 Answer 1

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .