Have you ever asked someone a question only to find that they asked you the same question a few months earlier? Well that happened in our research group today when Michael and I knocked on Pablo Spiga’s door to ask him whether he knows of a particular type of strongly regular Cayley graph. Deja vu immediately hit us, and the rest is a shameful example of a poor memory. Anyway, here is the problem that the three of us do not know the answer to, but for which someone out there might enlighten us.

Does there exist a strongly regular Cayley graph Cay(G, S) where G is a nonabelian simple group?

March 9, 2010 11:46 am

The answer (which I discovered when Pablo originally asked me the question) is trivially yes. Let G be a nonabelian simple group, H a proper subgroup of G and $S=G\backslash H$. Then $Cay(G,S)$ is the complete multipartite graph with $|G:H|$ parts of size $|H|$. These are not really interesting examples so the question should really be “Are there any others?”

March 10, 2010 10:13 am

When I first asked whether there exists a strongly regular graph of the form $\Gamma=Cay(T,S)$, for some non-abelian group $T$, I was really interested in the case that $Aut(\Gamma)$ is primitive on the vertices of $\Gamma$.

By a theorem of Liebeck-Praeger-Saxl, if a non-empty and non-complete Cayley graph $Cay(T,S)$, where $T$ is a non-abelian simple group, has primitive automorphism group then either $S$ is the union of $T$-conjugacy classes or $T=Alt(p^2-2)$ (for some prime $p\equiv 3\mod 4$). In this theorem there is no assumption on $\Gamma$ to be strongly regular.

In the case of strongly regular graphs, only the former case of the previous theorem is interesting, that is, $S$ is a union of conjugacy classes. I conjecture that

Conjecture. There exists no non-complete and non-empty strongly regular graph $\Gamma=Cay(T,S)$, where $T$ is a non-abelian simple group and $S$ is a union of conjugacy classes.

(1) By a result of Bannai, for a counterexample to the previous conjecture, the group $T$ cannot be $PSL(2,q)$.

(2) By a simple character theoretic argument one can show that, for a counterexample to the previous conjecture, there exists no prime $p$ dividing the order of every element in $S$.

3. May 2, 2010 7:00 pm

Isn’t it true that in such a case the automorphism group of your graph will be much bigger, namely, the stabilizer of a vertex will contain $G$ as a subgroup (acting by conjugation)?
So you basically seem to be asking whether it is possible that in the assoication scheme of the conjugacy classes of $G$ there is a primitive rank 3 association scheme.