Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Brendan McKay Feb 23 '12 at 23:27
    
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}$... –  Antoine Feb 24 '12 at 17:18
    
Sorry, please discard my comment. –  Brendan McKay Feb 25 '12 at 7:41
    
If $S \cup S^{-1}$ generates the group then so does $S$, right? (In my world the subgroup generated by a given set is the least subgroup that contans it.) –  Andrej Bauer Feb 25 '12 at 19:08
1  
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. –  Joel David Hamkins Feb 26 '12 at 14:55

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
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 –  Gerhard Paseman Feb 27 '12 at 8:54
    
Yes, it is for undirected graphs. –  Tara Brough Feb 27 '12 at 9:57
    
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. –  Antoine Mar 1 '12 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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