Consider the group $G=\mathbb{Z}_2^3$ with generators $S=\{e_1,e_2,e_3\}$ with $e_1=(1,0,0),e_2=(0,1,0),e_3=(0,0,1)$.

The Cayley graph $\text{Cay}(G,S)$ is the 3D hypercube graph. It's line graph $\Gamma$ is the $4$-regular Cuboctahedron graph. This graph is the Cayley graph of $A_4$ with generators $g=(1 2 3), h=(234)$ (as noted here).

I want to understand the fact the that $\Gamma$ is the Cayley graph of $A_4$ (or some other group) through the Cayley graph structure of $\text{Cay}(G,S)$. I will try to construct a group $H$ and a set $T$ of $4$ generators such that $\Gamma=\text{Cay}(S,T)$. We will probably have $H\cong A_4$.

So, as the elements of $H$ I'm taking the elements of $G$ "modulo" the generators in $S$. I use the following notation for these $12$ elements:

?00, ?01, ?10, ?11, 0?0, 0?1, 1?0, 1?1, 00?, 01?, 10?, 11?

Next, I would to define the multiplication on these $12$ elements and choose the set of $4$ generators $T\subset H$.

Who are the neighbors of 00? in $\Gamma$? They are ?00, 0?0, ?01, 0?1. So, the $4$ generators must be $00?^{-1}\cdot?00$ and $00?^{-1}\cdot0?0$ and $00?^{-1}\cdot?01$ and $00?^{-1}\cdot0?1$.

Similar relations should hold for the neighbors of all other vertices of $\Gamma$. So we have many equations describing the $4$ generators, although they don't say which generator is which.

I'm a little stuck here. I've listed some required conditions, but I don't know how to complete this to a specific group structure and $4$ generators.

What is a (relatively easy to describe) way to give those $12$ elements a group structure and choose $4$ generators such that the resulting Cayley graph is $\Gamma$ (the line graph of $\text{Cay}(G,S)$)?

I hope I made it clear that what I'm looking for is a group strucutre easy to describe in terms of the names of these 12 elements, as given.

  • $\begingroup$ I think one key point to understand is that the Cayley graph is effectively showing you, not so much the group itself, but the group's action on itself by means of its products - and more specifically, by means of the actions of the generators on arbitrary elements of the group. $\endgroup$ Jun 12, 2013 at 18:04
  • $\begingroup$ @StevenStadnicki: I understand this fact (I think). I also understand that there cannot be a completely natrual way to describe such a group. Because, for instance, one has to choose the identity element of the group and thus break symmetry. Still, if we could say "make these 3 artbitrary choices and now you have a natural way to describe such group" that could be good for me. $\endgroup$
    – Alex
    Jun 12, 2013 at 18:07

1 Answer 1


Note that $\mathbb{Z}_2^3$ acts naturally on your set $H$ of 12 elements, by addition. For example, $?01+010=?11$ and $?01+100=?01$. Next, note that $S_3$ also acts on $H$, by permuting the coordinates. For example, if we apply the cyclic rotation $(123)$ to $?01$, we get $1?0$. It's not hard that, together, this gives us an action of $\mathbb{Z}_2^3\rtimes S_3\cong S_4$. Simply take $A_4$ inside there, and check that this is a regular action, so you can identify your set with $A_4$. For the connection set, you can take any two inverse pairs of elements of order $3$.


You must log in to answer this question.

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