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.

$\endgroup$
10
  • 2
    $\begingroup$ do you consider finite groups or arbitrary groups? do you require the generating subsets be finite? $\endgroup$
    – YCor
    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$ 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$ Aug 26, 2013 at 20:06
  • 3
    $\begingroup$ @AlainValette: What about finite cyclic groups of order $>4$? $\endgroup$
    – Stefan Kohl
    Aug 26, 2013 at 21:05
  • 2
    $\begingroup$ @Stefan: I defy you to find other examples! :-) $\endgroup$ Aug 26, 2013 at 21:19

4 Answers 4

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.

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

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

$\endgroup$
3
  • $\begingroup$ The nonabelian group was not assumed to be free... $\endgroup$ Aug 26, 2013 at 17:54
  • $\begingroup$ @AntonPetrunin: but how to read the question, if the nonabelian group cannot be chosen? $\endgroup$
    – Stefan Kohl
    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$ 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.

$\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
    Jan 10, 2019 at 14:29
  • $\begingroup$ I didn't notice that. Thanks for mentioning. $\endgroup$
    – user52949
    Jan 10, 2019 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.