Discrete Math, Second Series, 4th Problem Set (July 25)
REU 2003

Instructor: Laszlo Babai
Scribe: Mridul Mehta

We focus our attention on automorphism groups of regular solids. A tetrahedron is just another way of representing the complete graph on 4 vertices i.e., $K_4$. The automorphism group $\textrm{Aut}(K_4) = S_4$. More generally, we have $\textrm{Aut}(K_n) = S_n$, where $K_n$ is the complete graph on $n$ vertices.

Next, we consider a cube. We may label the vertices of the cube so that the four in the top face are $1, 2, 3$ and $4$, while the diagonally opposite ones in the bottom face are $1', 2', 3'$ and $4'$ respectively. $\textrm{Aut}($cube $) = S_4 \times {\mathbb{Z}}_2$. Here the nonidentity element of ${\mathbb{Z}}_2$ corresponds to the central involution (i.e., reflection about the center of the cube) which is orientation reversing, while elements of $S_4$ correspond to the orientation preserving automorphisms of the cube.

By considering the action on pairs of opposite vertices of the cube (the main diagonals of the cube) we obtain the map Aut$($cube$) \to S_4$. The kernel of this map is $<$central reflection$>$. The image is all of $S_4$, so the map is onto. To see this, we define $\rho$ as a rotation about the vertical axis of the cube, and $\tilde{\rho}$ as the corresponding element of $S_4$ induced by $\rho$. Then $\rho$ permutes the main diagonals so that $\tilde{\rho}(\{i,i'\}) = (\{i+1,(i+1)'\})$ mod $4$. Similarly, if we let $\sigma$ be rotation about the diagonal $(1,1')$ by $120^{\circ}$, then the induced permutation $\tilde{\sigma}$ permutes the other three diagonals. The next exercise completes the argument.

Definition 0.1   The semidirect product of groups $K$ and $L$ with respect to $\alpha: K\to \textrm{Aut}(L)$ is the group $G = L \rtimes_{\alpha} K$ defined as the set $\{(l,k)\colon l\in L, k\in K\}$ with the operation $(l,k)(l',k') = (l{l'}^{\alpha(k)}, kk')$.

Definition 0.2   Let $G \le S_k$ and $H$ be any abstract group. The wreath product of $H$ by $G$ is defined to be $H\wr G = H^k \rtimes_{\alpha} G$ where $\alpha:G\to \textrm{Aut}(H^k)$ is the permutation action of $G$ on the $k$ components of $H^k$.

Let $X = X_i \cup \cdots \cup X_k$ be a graph with connected components $X_i$ and $X_i \cong X_j$ for all $1 \le i, j \le k$. Then Aut $(X) = \textrm{Aut}(X_1)\wr S_k$.

If $G \le S_k$ and $H \le \textrm{Sym}(\Omega)$, then the wreath product $H\wr G$ naturally acts on $\Omega_1 \dot{\cup}\cdots \dot{\cup} \Omega_k$ ( $\vert\Omega_i\vert = \vert\Omega\vert$). Here $H_i$, the $i$th component of $H^k$ acts on $\Omega_i$, and $G$ permutes the $H_i$. In this case, $H\wr G \le S_{kl}$ (where $l$ is the degree of $\textrm{Sym}(\Omega)$). This is called the ``imprimitive representation'' of $H\wr G$.

Remark 0.3   $H^k \triangleleft H\wr G$, $G\le H\wr G$, and $(H\wr G)/H^k \cong G$.

Let $Q_n$ be the graph of the $n$-cube. So $\vert Q_n\vert = 2^n$, and we may think of the vertices of this graph as elements of $\{0,1\}^n$, i.e., strings of length $n$ consisting of 0s and $1$s. We define the Hamming distance between two strings of equal length to be the number of places where they differ. Two vertices in $Q_n$ will be adjacent if their Hamming distance is 1.

Switching coordinates of vertices independently corresponds to reflections about various planes which shows that $({\mathbb{Z}}_2)^n \le \textrm{Aut}Q_n$. Similarly, permuting the positions of coordinates corresponds to rotations about different lines, which gives us $S_n \le \textrm{Aut}(Q_n)$.

Remark 0.4   $({\mathbb{Z}}_2)^n \triangleleft \textrm{Aut}(Q_n)$ and $\textrm{Aut}(Q_n)/({\mathbb{Z}}_2)^n \cong S_n$.

The ``primitive representation'' of $H\wr G$ is the action of $H\wr G$ on $\Omega_1 \times \cdots \times \Omega_k = \Omega^k = \{(a_1, \ldots, a_k)\colon a_i \in \Omega\}$ given by $(a_1,\ldots, a_k)^{(h_1,\ldots, h_k; g)} = (a^{h_1}_{1^{g^{-1}}},\ldots, a^{h_k}_{k^{g^{-1}}})$.

Corollary 0.5   $S_4 \times {\mathbb{Z}}_2 \cong {\mathbb{Z}}_2\wr S_3$.

The octahedron is the dual of the cube. Hence its automorphism group is the same as that of the cube.

Aut$($Dodecahedron $) = A_5 \times {\mathbb{Z}}_2$. Here, as before, the element in ${\mathbb{Z}}_2$ is the central reflection and $A_5$ is the subgroup of the orientation preserving automorphisms.