next up previous
Next: About this document ...

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 % latex2html id marker 1399
$ \textrm{Aut}(K_4) = S_4$. More generally, we have % latex2html id marker 1401
$ \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. % latex2html id marker 1415
$ \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.


\begin{exercise}
% latex2html id marker 710If $A \in M_3({\mathbb{R}})$, then ...
... of
all $n \times n$\ matrices with entries from ${\mathbb{R}}$.)
\end{exercise}


\begin{exercise}
% latex2html id marker 715In ${\mathbb{R}}^3$, every orientat...
...ansformation $A$\ is {\em orientation preserving}
if $\det(A)>0$.
\end{exercise}

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.


\begin{exercise}
% latex2html id marker 718$S_4 = <\tilde{\rho}, \tilde{\sigma}>$.
\end{exercise}


\begin{exercise}
% latex2html id marker 720If $C$\ is any centrally symmetric ...
...Here
$\textrm{Aut}^+(C)$\ is the orientation preserving subgroup.
\end{exercise}


\begin{exercise}
% latex2html id marker 724Show that the above statement fails...
...en $(\rho_0)^{\tau^i} =
(\tau^i)^{-1}(\rho_0)(\tau^i) = \rho_i$.
\end{exercise}


\begin{exercise}
% latex2html id marker 730Find a finite group $G$\ such that ...
...\; A\le G)(G = Z(G)\times A)$.
Find the smallest such group $G$.
\end{exercise}

Definition 0.1   The semidirect product of groups $ K$ and $ L$ with respect to % latex2html id marker 1460
$ \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')$.


\begin{exercise}
% latex2html id marker 732With the above definition, show tha...
...iangleleft G$; and
\ (d)\ $K \cong \{(1,k)\colon k\in K\} \le G$.
\end{exercise}

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 % latex2html id marker 1479
$ \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 % latex2html id marker 1495
$ (X) =
\textrm{Aut}(X_1)\wr S_k$.

If $ G \le S_k$ and % latex2html id marker 1499
$ H \le \textrm{Sym}(\Omega)$, then the wreath product $ H\wr
G$ naturally acts on % latex2html id marker 1503
$ \Omega_1 \dot{\cup}\cdots \dot{\cup} \Omega_k$ ( % latex2html id marker 1505
$ \vert\Omega_i\vert = \vert\Omega\vert$). Here $ H_i$, the $ i$th component of $ H^k$ acts on % latex2html id marker 1513
$ \Omega_i$, and $ G$ permutes the $ H_i$. In this case, $ H\wr G \le S_{kl}$ (where $ l$ is the degree of % latex2html id marker 1523
$ \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 % latex2html id marker 1549
$ ({\mathbb{Z}}_2)^n \le \textrm{Aut}Q_n$. Similarly, permuting the positions of coordinates corresponds to rotations about different lines, which gives us % latex2html id marker 1551
$ S_n \le \textrm{Aut}(Q_n)$.


\begin{exercise}
% latex2html id marker 735$\textrm{Aut}(Q_n) = {\mathbb{Z}}_2 \wr S_n$.
\end{exercise}

Remark 0.4   % latex2html id marker 1554
$ ({\mathbb{Z}}_2)^n \triangleleft \textrm{Aut}(Q_n)$ and % latex2html id marker 1556
$ \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 % latex2html id marker 1562
$ \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.


\begin{exercise}
% latex2html id marker 742Aut$($Octahedron$)\cong $Aut$($Cube$)$.
\end{exercise}


\begin{exercise}
% latex2html id marker 744Generalize the above exercise to $n$-dimensions.
\end{exercise}

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.


\begin{exercise}
% latex2html id marker 748Show that the action of the rotatio...
...triples of perpendicular axes connecting opposite edges
is $A_5$.
\end{exercise}


\begin{exercise}
The action on the 10 pairs of opposite vertices in the dodecahedron is
primitive.
\end{exercise}


\begin{exercise}
% latex2html id marker 752Show that the automorphism group of...
...(so that two pairs are
adjacent if they are completely disjoint).
\end{exercise}



next up previous
Next: About this document ...
Varsha Dani 2003-08-04