Skip to content

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?

4 Comments leave one →
  1. Michael Giudici permalink
    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?”

  2. Pablo Spiga permalink
    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.

    Two comments.

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

    • ?ablo permalink
      May 7, 2010 10:34 am

      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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: