Letters like $G$ will denote groups. The notation $H\le G$ means that $H$ is a subgroup of $G$.
Letters like $X$ will denote graphs. A graph $X = (V, E)$ will be undirected by definition. We will use the word digraph to refer to directed graphs.
Recall that there are five Plantonic solids: tetrahedron, cube, octahedron, dodecahedron and icosahedron. The automophism group of a Platonic solid is the set of Euclidean isometries (rotation and refelction) leaving it invariant.
Exercise 1.1:
$\aut(\mathrm{Tetrahedron})\cong S_4$.
Fix a basis of $\R^n$, a linear transformation $A\in\gl(n, \R)$ can be realized by an invertible matrix $M$. $A$ is called orientation preserving if $\det(M)>0$.
Exercise 1.2:
(a) If $S$ is a full-dimensional subset of $\R^n$, then the group $G$
of the isometries of $S$ has a subgroup of index $\leq 2$ consisting
of all orientation preserving elements. Denote this subgroup of
$\aut(S)$ as $\aut^+(S)$.
(b) Suppose $n$ is odd, $S$ is a full-dimensional bounded subset of
$\R^n$, $S=-S$. Then $\aut(S)=\aut(S)^+\times C_2$. Note that the
boundedness condition can not be omitted.
Exercise 1.3:
(a) $\aut^+(\mathrm{Tetrahedron})\cong A_4$.
(b) $\aut^+(\mathrm{Cube})\cong S_4$.
(c) $\aut(\mathrm{Cube})\cong S_4\times C_2$.
Give a graph $X$, an automorphism of $X$ is a permutation of the vertices that preserves the edge relation.
Exercise 2.1:
(a) Find a graph $X$ such that $\aut(X)\cong C_3$.
(b) (Frucht's theorem, 1938) $(\forall G)(\exists X)(\aut(X)\cong G)$.
Exercise 2.2: If $X$ is a 3-regular connected graph, $e$ is an edge in $X$, then $\aut(X)_e$ (the automorphisms preserving $e$) is a 2-group.
Exercise 2.3: If $\aut(X)\cong Q_8$ ($Q_8$ is the quaternion group), then $X$ is not planar.
Exercise 2.4: If the characteristic polynomial of the adjacency matrix of $X$ is irreducible over $\mathbb{Q}$, then $\aut(X)$ is trivial.
Exercise 2.5: $X$ is connected graph, and every vertex has degree $\leq d$. Then $\aut(X)_e\in \Gamma_{d-1}$. Here $\Gamma_{k}$ is the set of groups whose composition factors are subgroups of $S_{k}$
Let $A\leq \sym(U)$, and $B\leq \sym(V)$. Let $\Omega=U\times V$. We will construct the wreath product $G = A\wr B\leq \sym(\Omega)$.
First let us describe two groups, $H$, $B^*\leq \sym(\Omega)$. For a given $v\in V$, $A$ can act on $U\times\{v\}$ by its action on $U$. Denote this action by $A(v)\leq \sym(U\times V)$. Then $H$ is defined as $\prod_{v\in V} A(v)\cong A^V$. Given $\pi\in B$, it induces an action $\pi^*$ on $\Omega$ by sending $(u,v)$ to $(u, v^\pi)$. Let $B^*=\{\pi^*\mid \pi\in B\}\leq\sym(\Omega)$. The wreath product $G=A\wr B$ is the defined as $\langle H, B^* \rangle$, the group $G$ generated by $H$ and $B^*$.
Formally, for $(a_1, \dots, a_m), (a'_1, \dots, a'_m)\in H$, and $b, b'\in B$, we define the product $ (a_1, \dots, a_m; b)(a'_1, \dots, a'_m; b') = ( a''_1, \dots, a''_m; b'')$, where $b'' = b b'$, and $a''_i = a_i a'_{i^{b^-1}}.$
Exercise 3.1 Show that $H\triangleleft G$. The follwowing 2 exercises are hints to this one.
Exercise 3.2: Recall the definition of a normal subgroup: $N\triangleleft G\ :\ (\forall g\in G)(g^{-1}Ng = N).$ Prove that it sufficient to verify the above for a set of generators of $G$.
Definitions: $g$ normalizes $N$ if $g^{-1}N g = N$.
Exercise 3.3 : Prove that $H$ normalizes $H$ and $B^*$ normalizes $H$.
Exercise 3.4 : If $K, L\leq G$ such that $KL = G$ and $K\cap L = 1$, then $|G|= |K||L|$.
Exercise 3.5 If $K, L\leq G$, $KL \leq G \Leftrightarrow KL=LK$.
Exercise$^o$ 3.6 Find two subgroups in $S_3$ such that their product is not a subgroup.
Exercise 3.7 Show that if $G = \langle K, L \rangle$, where $K\triangleleft G$, and $L\leq G$, then $G = KL$.
Corollary 3.8 $A\wr B = HB^*$.
Exercise 3.9 Explain that the action of $A\wr B$ on $U\times V$ is imprimitive.
Exercise 3.10:
(a) Show that $\aut(\mathrm{cube})\cong
S_4\times S_2\cong C_2\wr S_3$.
(b) Let $Q_n$ be the
$n$-dimensional cube, that is $Q_n=\{x\in\R^n\mid\norm{x}_{\infty}=1
\}$. Show that $\aut(Q_n)\cong C_2\wr S_n$.
Exercise 3.11:
(a) Let $X$ be a connected graph, then $kX$ is the graph consisting of
the disjoint union of $k$ copies of $X$. Show that $\aut(kX)\cong
\aut(X)\wr S_k$.
(b) As a consequence, given any graph (possibly not
connected), its automorphism group is direct product of wreath
products, where the direct factors are based on grouping isomorphic
copies together.
Please refer to Petersen graph for the definition of Petersen graph.
Exercise 4.1:
(a) Show that $\aut(\mathrm{Petersen graph})$ has a subgroup of order
30. Hint: dihedral group of order 10.
(b) Show that $\aut(\mathrm{Petersen graph})\cong S_5$. Hint: Try
to identify triples of edges preserved by automorphisms. Some drawing
of Petersen's graph
in this page may
help you.
Next we review the symmetries of dodecahedron and note a connection with Petersen's graph.
Exercise 4.2:
(a) $\aut(\mathrm{Dodecahedron})\cong A_5\times C_2$, and $\aut^+(\mathrm{Dodecahedron})\cong A_5$.
(b) Explain that $A_5\times C_2\not\cong S_5$.
(c) Explain that Petersen graph can be embedded to the projective
plane by identifying opposite vertices of the dodecahedron.
Given a graph $X=(V, E)$, the line graph of $X$, denoted $L(X)=(E, F)$, is a graph whose vertices are the edges of $X$. Two edges (vertices in $L(X)$) are adjacent if they share a vertex in $X$. Note that every automorphism of $X$ naturally induces an automorphism of $L(X)$.
Exercise 5.1:
(a) Show that if $(\forall v\in V)(\mathrm{deg}(v)\geq 4)$, then $\aut(X)\cong \aut(L(X))$.
(b) Show that the natural homomophism from $\aut(X)$ to $\aut(L(X))$ can be not onto and not faithful.
(c) Prove that the complement of $L(K_5)$ is isomorphic to Petersen graph.
A tournament is a digraph obtained by assigning a direction to every edge in $K_n$. Note that the number of tounaments on $n$ given vertices is $2^{\binom{n}{2}}$.
Exercise 5.2: For a tournament $T$, $\aut(T)$ is solvable. Recall that the Feit-Thompson theorem states that every finite group of odd order is solvable. Show that the Feit-Thompson theorem implies the above and vice versa.
Exercise 6.1:
(a) If $P$ is a Sylow $p$-subgroup of $S_{p^k}$, then $P\cong C_p\wr C_p\wr\dots\wr C_p$ ($k$ times).
(b) Show that te automorphism group of the depth-$h$ $k$-ary tree is
$S_k\wr S_k\wr\dots\wr S_k$ ($h$ times). In particular, note that the
automorphism group of depth-$h$ binary tree is isomorphic to the Sylow
2-group of $S_{2^h}$.
Let $\cT=\{\aut(T)\mid T \text{ is a tree}\}$. We remark that $\cT$ contains identity (trivial automorphism), and is closed under direct product and wreath product.
Exercise 6.2:
(a)Exhibit a non-trivial tree with trivial automorphism group.
(b) Show that $\cT$ is closed under direct product. (Hint:
the center of a tree is a vertex or an edge fixed by all
automorphisms. Show that every tree has a center.)
(c) Show that $\cT$ is closed under wreath product.
Given a group $G$ and $S\subseteq G$, $1\not\in S$, the Cayley graph $\Gamma(G, S)=(G, \{\{g, sg\}\mid g\in G, s\in S\})$.
Exercise 7.1:
(a) $\Gamma$ is vertex transitive. (Recall that a graph $G$
is vertex-transitive if for any pair of vertices $v$ and
$v'$, there exists $\phi\in\aut(G)$ such that $\phi(v)=v'$.)
(b) $\Gamma$ is connected if and only if $S$ generates $G$.
(c) If $S$ is a minimal set of generators of $G$, then $K_{3,
5}\not\subseteq\Gamma$.
(d) If $\Gamma(C_p, S_1)\cong\Gamma(C_p, S_2)$, then $(\exists c,\,
c\nmid p)(S_2=cS_1)$.
The diameter of a group $G$ w.r.t. $S\subseteq G$ is $\mathrm{diam}(G, S)=\mathrm{diam}(\Gamma(G, S))$.
Exercise 7.2:
(a) Prove $\langle (12), (12\dots n)\rangle=S_n$.
(b) Show that $\mathrm{diam}(S_n, \{(12), (12\dots n)\})=\Theta(n^2)$.
A finite projective plane is a triple of sets $(P, L, I)$, where $P$ is the set of points, $L$ the set of lines, and $I\subseteq P\times L$ describes the incidence relation of a point being on a line. Such a triple is a finite projective plane if it satisfies the followin axioms: (1) for every two points there is a unique line passing them; (2) every two lines intersect at a unique point; (3) there are four points not on a line.
It can be shown that on a finite projective plane, there exists $n$ such that every line contains $n+1$ points and every point lies on $n+1$ lines. This $n$ is called the order of the projective plane. The automorphism group of a projective plane is the set of permutations of vertices preserving collinearity.
The Fano plane is the smallest finite projective plane of order 2. See Fano plane on Wikipedia.
Exercise 8.1: Let $F$ be the Fano plane. Prove that $|\aut(F)|=168$. (In fact, $\aut(F)\cong PSL(3, 2)$, which is the next smallest simple group after $A_5$.)
Exercise 8.2:
(a) For every prime power $q$, construct a projective plane of order
$q$. (Hint: for $v\in\F_q^3$, $v\neq \overrightarrow{0}$, let
$\underline{v}=\{u\in\F_q^3\mid u=r\cdot v, r\in\F_q, r\neq
0\}$. $\underline{v}$ is called the homogeneous coordinate of
$v$. $P$ and $L$ will be homogeneous coordinates.)
Planes constructed in such a way are called Galois Planes.
(b) Show that the Fano plane can be constructed as above. Describe
the homogeneous coordinates and lines on the Fano plane.
Exercise 8.3: Given a projective plane $L$ of order $n$, and $L'\subsetneq L$ is a subplane. Then $L'$ has order $\leq\sqrt{n}$, and this is tight infinitely often.
Exercise 8.4: For a projective plane $L$, prove that $|\aut(L)|\leq n^{O(\log\log n)}$. Verify this for Galois planes.
Given a vector space $V=\F_q^n$, the Gaussian binomial coefficient $\gbinom{n}{k}_q$ is defined to be the number of $k$-dimensional subspaces of $V$.
Exercise 9.1: Calculate Gaussian binomial coefficient $\gbinom{n}{k}_q$ from its definition. Prove that $\lim_{q\to 1^+}\gbinom{n}{k}_q=\binom{n}{k}$.
Exercise 9.2: Calculate $|\gl(n, q)|$, $|\mathrm{SL}(n, q)|$ and $|\mathrm{PSL}(n, q)|$.