# Strongly regular Cayley graphs

March 8, 2010

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?

Advertisements

4 Comments
leave one →

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 . Then is the complete multipartite graph with parts of size . These are not really interesting examples so the question should really be “Are there any others?”

When I first asked whether there exists a strongly regular graph of the form , for some non-abelian group , I was really interested in the case that is primitive on the vertices of .

By a theorem of Liebeck-Praeger-Saxl, if a non-empty and non-complete Cayley graph , where is a non-abelian simple group, has primitive automorphism group then either is the union of -conjugacy classes or (for some prime ). In this theorem there is no assumption on to be strongly regular.

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

Conjecture. There exists no non-complete and non-empty strongly regular graph , where is a non-abelian simple group and is a union of conjugacy classes.

Two comments.

(1) By a result of Bannai, for a counterexample to the previous conjecture, the group cannot be .

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

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 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 there is a primitive rank 3 association scheme.

Yes, this is what I am asking. I do know the answer (for instance) in the case that G=PSL(2,q) (so assuming what G is, but not hypothesis on S) or in the case that every element of S has order divisible by some fixed prime p (so no hypothesis on G). In particular, in these two cases no such an association scheme exists. I conjecture that they do not exist in a generic finite simple group.