17
$\begingroup$

There are many examples of two non-isomorphic groups with the same Cayley graph. If the graph is non-oriented, asking for the generating set to be minimal does not make the task much harder. However, I was unable to answer the following

$\textbf{Question:}$ Say a set $S$ inside a group is "mag" if it is minimal (for the inclusion) among sets that generate the group ($\textit{i.e.}$ such that the words in $S \cup S^{-1}$ give the full group). Find two non-isomorphic groups $G$ and $H$ such that the oriented Cayley graphs of $G$ and $H$ with respect to $S \subset G$ and $T \subset H$ are isomorphic, given that $S$ and $T$ are "mag".

Apologies in advance if the answer is well-known...

PS: Here by Cayley graph of $G$ w.r.t. $S$, I mean the graph whose vertices are $G$ and $(g,h)$ is an edge if and only if $\exists s \in S, g =hs$. (There are two conventions, but it matters little for the question.) The point being that if $(g,h)$ is an edge then $(h,g)$ need not be one.

PPS: given minimality of $S$ and finiteness of the group, $S$ will usually be anti-symetric.

Here are examples. Take $G = \mathbb{Z}$ and $ H= (\mathbb{Z}/2 \mathbb{Z}) *(\mathbb{Z}/2 \mathbb{Z})$. For $H$, picking $ \lbrace a,b \rbrace$ the resulting Cayley graph is going to be infinite unoriented path ("two-way" infinite street). For $G$, you could pick $S =\lbrace 1\rbrace$ or $S = \lbrace -1\rbrace$ but not $S = \lbrace -1, 1\rbrace$. In either case, the resulting (oriented) Cayley graph is going to be a infinite unorientd path ("one-way" infinite street).

There might be two questions: for finite groups and infinite groups. I suspect one could find them more easily by looking at infinite groups.

$\endgroup$
19
  • 1
    $\begingroup$ Two distinct 2-transitive groups of the same degree will suffice, as both Cayley graphs will be complete graphs. I assume you'd like more interesting examples, though. $\endgroup$ Feb 23, 2012 at 23:27
  • $\begingroup$ I think I just don't understand your statement. If the resulting graph is complete and $S$ is minimal as said above, then (unless I am mistaken, and this might very well be the case) it means every element is needed to generate the group and also that the product of two (non-trivial) elements should be the identity (otherwise it would mean this element would be generated by others. This forces the group to be $\mathbb{Z}/ 2\mathbb{Z}$... $\endgroup$
    – ARG
    Feb 24, 2012 at 17:18
  • $\begingroup$ Sorry, please discard my comment. $\endgroup$ Feb 25, 2012 at 7:41
  • 1
    $\begingroup$ Thanks for this comment. If the groups are finite (or is infinite, but generated by elements of finite order), then this assumption is indeed superfluous. I edited the post in order to clarify this point... I forgot to specify that I could not even find a counter-example when the groups are infinite. $\endgroup$
    – ARG
    Feb 26, 2012 at 10:44
  • 1
    $\begingroup$ You talk about the Cayley graphs of $G$ with respect to $S$ and $H$ with respect to $T$ being "identical", but since they are on different vertex sets, they cannot be actually identical. I guess you mean isomorphic rather than identical. $\endgroup$ Feb 26, 2012 at 14:55

2 Answers 2

5
$\begingroup$

If we consider the dihedral group of order 12, $G = \langle a, b \mid a^2 = b^2 = (ab)^6 = e \rangle$, then the Cayley graph corresponding to $\{ a, b \}$ is the cyclic graph on 12 vertices with edges labeled alternately by $a$ and $b$. We may then consider $H_1 = G \times \mathbb Z/2 \mathbb Z$ and $H_2 = G \rtimes \mathbb Z/2 \mathbb Z$ where the copies of $\mathbb Z/ 2 \mathbb Z$ are generated by $c$ and $d$ respectively, and where $d$ acts by $d a d = b$, $d b d = a$. Then the Cayley graph of $H_1$ with respect to $\{ a, b, c \}$ consists of two copies of cyclic graphs of order 12 with edges labeled by $c$ connecting the two graphs. Since $d$ just interchanges $a$ and $b$ we have that the Cayley graph of $H_2$ with respect to $\{ a, b, d \}$ can be obtained from the Cayley graph of $H_1$ by just relabeling the second copy of the cyclic graph, so that the two Cayley graphs will be isomorphic.

Unfortunately, the generating set for $H_2$ is not minimal since by the definition of $d$ we have $b \in \langle a, d \rangle$. This can be fixed however by taking two automorphisms $c$ and $d$ which are complicated enough so that this doesn't occur.

Specifically, we can let $c$ act on $G$ by $cac = ababa$, and $cbc = babab$, and we can let $d$ act on $G$ by applying $c$ and then interchanging $a$ and $b$, i.e., $dad = babab$, and $dbd = ababa$. It's not hard to see that these indeed define order two automorphisms of $G$, and for the same reason as above we have that the Cayley graphs of $H_1$ and $H_2$ will be isomorphic.

It is also not hard to check that we now have $| \langle a, c \rangle | = | \langle b, c \rangle | = 12 < 24$ and $| \langle a, d \rangle | = | \langle a, d \rangle | = 8 < 24$ so that the generating sets are now minimal. Moreover, the groups $H_1$ and $H_2$ will not be isomorphic, this can be seen for instance by counting the number of elements of order 2, (I counted 15 for $H_1$ and 9 for $H_2$, but I've omitted the tedious details).

$\endgroup$
0
$\begingroup$

Here are a couple of papers I found by googling "nonisomorphic groups with same Cayley digraph":

Morris, J. (1999), Isomorphic Cayley graphs on nonisomorphic groups. Journal of Graph Theory, 31: 345–362. (Available here: http://www.cs.uleth.ca/~morris/Research/AnneExtension.pdf)

and

Kovács, I. and Servatius, M. (2011), On Cayley digraphs on nonisomorphic 2-groups. Journal of Graph Theory. doi: 10.1002/jgt.20625,

which apparently extends Morris's results.

I haven't looked at these in enough detail to see whether they will answer your question, but it looks like Morris's paper would be a good place to start.

$\endgroup$
3
  • $\begingroup$ Clara Loeh has recently submitted a paper on arxiv for the case of finitely generated Abelian groups. I have not looked at the paper, but suspect it is for undirected graphs. Gerhard "Ask Me About System Design" Paseman, 2012.02.27 $\endgroup$ Feb 27, 2012 at 8:54
  • $\begingroup$ Yes, it is for undirected graphs. $\endgroup$ Feb 27, 2012 at 9:57
  • $\begingroup$ Thanks for the further comments (question corrected) and apologies as I did not have time to look at the papers... My intuition was somehow against Abelian groups being potential counter-examples, but I could easily be wrong. $\endgroup$
    – ARG
    Mar 1, 2012 at 18:55

Your Answer

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

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