Question regarding Cayley graph generated in GAP software

cayley-graphsfinite-groupsgapgraph theorygroup-theory

I have computed a semidirect product of $(\mathbb{Z}_5 \times \mathbb{Z}_5) \rtimes \mathbb{Z}_3$ in GAP as shown below.

gap> Z3:=Group((1,2,3));;

gap>  Z3gen:=GeneratorsOfGroup(Z3)[1];;

gap>  Z5:=Group((1,2,3,4,5));;

gap> h:=DirectProduct(Z5,Z5);;

gap>  Auts:=AutomorphismGroup(h);;

gap> AutsOfOrd3:=Filtered(Elements(Auts),elt->Order(elt)=3);;

gap> ExHom:=GroupHomomorphismByImages(Z3,Auts,[Z3gen],[AutsOfOrd3[1]]);
[ (1,2,3) ] -> [ [ (1,2,3,4,5), (6,7,8,9,10) ] -> [ (1,5,4,3,2)(6,10,9,8,7), (1,2,3,4,5) ] ]

gap> s:=SemidirectProduct(Z3,ExHom,h);;

After that I drew a Cayley graph for the semidirect product $s$.

gap> Read("C:/Users/kasuni/Desktop/Test1/UndirectedGeneratingSets.gap");

gap> LoadPackage("grape");;

gap> S:=IrredUndirGenSetsUpToAut(s);;

gap> S1:=S[1];;

gap> X1:=CayleyGraph(s,S1);

In the manual for grape package https://www.gap-system.org/Manuals/pkg/grape/doc/manual.pdf in page 12 it was described as

"if undirected=true (the default) then vertices $x, y$ are joined by an edge if and only if there is a $g$ in the list gens with $y = gx$ or $y = g^{−1}x$; if undirected=false then $[x, y]$ is an edge if and only if there is a
$g$ in gens with $y = gx$." under the description for Cayley graphs. There I observed that the multiplication by the elements from the generating set is from the left side.

But according to the usual definition for Cayley graphs,

"Let $G$ be a group and $S \subseteq G$ be a generating set of $G$. The Cayley digraph of $G$ with respect to $S$, $X=\overrightarrow{\operatorname{Cay}}(G,\: S)$ is a graph whose vertices are the elements of $G$ and there is an edge from $g$ to $gs$ whenever $g \in G$ and $s \in S$. The Cayley graph, $X=\operatorname{Cay}(G,\: S)$ is the undirected graph whose vertices are the elements of $G$ and there is an edge from $g$ to $gs$ and from $g$ to $gs^{-1}$ whenever $g \in G$ and $s \in S$."

the multiplication by the elements from the generating set is on the right side.

Does that mean that the Cayley graph generated by the GAP software is different from the Cayley graph we think of under usual definitions?

If I try to draw a Cayley graph by computing every and each point by thinking about the usual definition where there is an edge from $g$ to $gs$ whenever $g \in G$ and $s \in S$, and do computations in GAP as,

A:=Elements(s);
P1:=A[1]*S1[1];
P2:=P1*S1[1];
P3:=P2*S1[1];
P4:=A[1]*S1[2];
P5:=P4*S1[2]; etc.

will it generate a Cayley graph corresponding to the usual definition?

What is its relationship with the Cayley graph given by GAP system's CayleyGraph command?

Can someone please help me to clarify this question regarding the Cayley graphs?

Thanks a lot in advance.

Best Answer

One can argue what the "usual" definition is.

If one looks at the documentation for CayleyGraph

https://gap-packages.github.io/grape/htm/CHAP002.htm#SECT007

it says

The Cayley graph caygraph which is returned is defined as follows: the vertices (actually the vertex-names) of caygraph are the elements of $G$; if undirected=true (the default) then vertices $x,y$ are joined by an edge if and only if there is a $g$ in the list gens with $y=gx$ or $y=g^{−1}x$; if undirected=false then $[x,y]$ is an edge if and only if there is a $g$ in gens with $y=gx$.

Thus the graph is defined by left multiplication of the generators.

The (natural) reason for doing so, is that the group then acts by right multiplication on the Cayley graph. Right multiplication is the usual way (in articles in Group Theory or Algebraic Combinatorics) how a group acts, though some other areas of mathematics (and many undergraduate textbooks) seem to like action by left multiplication.

If you use the other convention, you get potentially a different Cayley graph. It is isomorphic to the Cayley graph for the inverse generating set by inverting the labels of all elements.

Related Question