11
$\begingroup$

It's the first question I post here :) I'm sorry if the question is too specific or if it's somehow repeating others.

In other words, my question is the following. Consider a Cayley graph $\Gamma$ of a non-abelian group. Consider also the family $\mathcal{F}$ of Cayley graphs of abelian groups. Is there $\Gamma$ such that, for all $\Gamma~' \in \mathcal{F}$, $\Gamma$ is not isomorphic to $\Gamma~'$?

I've read some interesting posts such as:

  • Non-isomorphic groups with the same oriented Cayley graph;
  • Does a Cayley graph on a minimal symmetric set of generators determine a finite group up to isomorphism?.

However, I haven't made any progress towards the answer.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ do you consider finite groups or arbitrary groups? do you require the generating subsets be finite? $\endgroup$
    – YCor
    Commented Aug 26, 2013 at 17:41
  • 2
    $\begingroup$ In a finite group you may choose all the elements as generators --- this way you get many examples. I do not know what happens if in addition you require that the set of generators is minimal. $\endgroup$
    – Anton Petrunin
    Commented Aug 26, 2013 at 17:52
  • 6
    $\begingroup$ The girth (= minimal length of a circuit) in an abelian Cayley graph, is at most 4 (as generators do commute). So as soon as your Cayley graph has a circuit of length >4, it does not come from an abelian group. $\endgroup$
    – Alain Valette
    Commented Aug 26, 2013 at 20:06
  • 3
    $\begingroup$ @AlainValette: What about finite cyclic groups of order $>4$? $\endgroup$
    – Stefan Kohl ♦
    Commented Aug 26, 2013 at 21:05
  • 2
    $\begingroup$ @Stefan: I defy you to find other examples! :-) $\endgroup$
    – Alain Valette
    Commented Aug 26, 2013 at 21:19

4 Answers 4

Reset to default
16
$\begingroup$

If I understand my own 1979 catalogue of small transitive graphs, this happens first at 12 vertices. The simplest example to describe (L10 in the catalogue): take the tetrahedon and cut off each of the corners to make a little triangle; the skeleton is a cubic cayley graph but not of an abelian group.

One very simple observation is that cayley graphs of abelian groups generally have lots of 4-cycles formed by edges $g$, $h$, $g^{-1}$, $h^{-1}$ from two of the generators. So, a cayley graph of degree at least 3 without 4-cycles is not a cayley graph of an abelian group. Like the example I gave.

Improve this answer
$\endgroup$
6
$\begingroup$

Choose your connection set $C$ so that the Cayley graph $\Gamma$ relative to $C$ is a graphical regular representation of $G$. Then the stabilizer of a vertex of $\Gamma$ is trivial. If $\Gamma$ was a Cayley graph for a second group $H$, the the order of $\mathrm{Aut}(\Gamma)$ would have order at least $|GH|$, and so its vertex stabilizers are non-trivial.

If $G$ is not abelian with exponent greater than four and not generalized dicyclic (google) and not one of 13 exceptional groups (with order at most 32), than it has a GRR (= graphical regular representation).

Edit: I should add that, the above exceptions aside, we expect that with probability close to 1 a randomly chosen connection set will work. This has been proved for nilpotent groups of odd order.

Improve this answer
$\endgroup$
5
$\begingroup$

Let's assume that we are talking about finitely generated groups. The Cayley graph of a finitely generated abelian group has always either 0, 1 or 2 ends, whereas for example the Cayley graph of a nonabelian free group of rank 2 has infinitely many ends, and is thus not isomorphic to the Cayley graph of any finitely generated abelian group. So the answer to your question is yes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The nonabelian group was not assumed to be free... $\endgroup$
    – Anton Petrunin
    Commented Aug 26, 2013 at 17:54
  • $\begingroup$ @AntonPetrunin: but how to read the question, if the nonabelian group cannot be chosen? $\endgroup$
    – Stefan Kohl ♦
    Commented Aug 26, 2013 at 17:59
  • $\begingroup$ Right, it is not clear, one way is in Godsil's answer --- for any nonabelian group there is a set of generators such that. $\endgroup$
    – Anton Petrunin
    Commented Aug 26, 2013 at 18:17
1
$\begingroup$

Choose a Cayley graph on a non-abelian group with girth more than $4$. It can not be a Cayley graph on an abelian group.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ You want it of valency $\ge 3$, too. By the way, this was already mentioned by Alain Valette as a comment to the question. $\endgroup$
    – YCor
    Commented Jan 10, 2019 at 14:29
  • $\begingroup$ I didn't notice that. Thanks for mentioning. $\endgroup$
    – user52949
    Commented Jan 10, 2019 at 18:11

You must log in to answer this question.

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