Tutorial 4
1. Consider the group D4 acting on the 2-banded 4-necklace (as
in the mid-sem examination). Consider the colouring of the beads
with the colours A or B, with the cost of A as 1 unit and that
of B as 2 units. Enumerate the number of necklaces of different
costs.
2. Let $T\times G\rightarrow T$ and $T\times H\rightarrow T$
be two actions of different groups on the same set $T$.
We say that the two actions commute, if $(t.g).h=(t.h).g$ for
all $t\in T$, $g\in G$ and $h\in H$. Show that if the actions
commute then the orbits in $T$ under the $G$-action go to
themselves under the $H$ action. In other words, if $t_1 $ and
$t_2 $ are in the same $G$-orbit, then for any $h\in H$, the
elements $t_1 .h$ and $t_2 .h$ are also in the same $G$-orbit.
3. Let us consider the notation of Problem 2 above. Let
$T=S\times S\times S$ as above. Define the action of $S_3 $ on
$T$ as follows. For an element $t=(i,j,k)$, and an element $\mu
\in S_3 $, the entries of $t$ are permuted as per $\mu $. Thus
if $\mu =(123)=(312)$ then $t.\mu =(k,i,j)$. Show that the action of
$S_3 $ commutes with the action of $S_n $ on $T$. Verify that
$S_3 $ moves orbits of $S_n $ to orbits of $S_n $.
4. Given a permutation $\sigma $ on $n$ letters, whose cycle
decomposition is into cycles of lengths $n_1 ,\ldots ,n_k $.
Compute the sign of this permutation in terms of this data.
5. For a graph $G(V,E)$, we say that $e,e'$ are related if there
is a cycle containing both $e$ and $e'$. Show that this is an
equivalence relation.
6. Let $G(V,E)$ be a general graph. Recall that "connectedness"
is an equivalence relation. Let $G$ split into $k$ connected
parts under this relation. Show that every maximal acyclic
subgraph of $G$ has $|V|-k$ edges.
7. (i) Show that a connected graph with $|V|-1$ edges must be a
tree.
(ii) Show that if $G$ is such that for any two vertices,
there is a unique path connecting them, then $G$ is a tree.