Please Login to access more options.

Problem 6 (Automorphisms Of A Square)

Consider the graph $\mathcal{G} = (V,E)$ drawn below. The vertex set is $V = \{1,2,3,4\}$ and the set of edges is $$E = \{\{1,2\},\{2,3\},\{3,4\},\{1,4\}\}.$$

Write down all the automorphisms of $\mathcal{G}$ (there are more than 4, but less than 10). Explain how you know you have listed every automorhpism of $\mathcal{G}$.

This problem continues in AutomorphismsOfASquare2.

Solution

Consider the graph $\mathcal{G}=(V,E)$ drawn below (Figure 1). The vertex set is $V=\{1,2,3,4\}$ and edges $E=\{\{1,2\},\{2,3\},\{3,4\},\{1,4\}\}$.


Figure 1: Graph $\mathcal{G}$.

We claim the following table lists the set of all automorphisms of $\mathcal{G}$ denoted $\text{Aut}(\mathcal{G})$. $$ \begin{array}{|c|c|} \hline \text{Rotations} & \text{Flips}\\ \hline \begin{matrix} R_0=\begin{pmatrix} 1&2&3&4\\\ 1&2&3&4 \end{pmatrix} \\ R_{90}=\begin{pmatrix} 1&2&3&4\\\ 2&3&4&1 \end{pmatrix} \\ R_{180}=\begin{pmatrix} 1&2&3&4\\ 3&4&1&2 \end{pmatrix} \\ R_{270}= \begin{pmatrix} 1&2&3&4\\ 4&1&2&3 \end{pmatrix} \end{matrix} & \begin{matrix} H=\begin{pmatrix} 1&2&3&4\\ 2&1&4&3 \end{pmatrix} \\ V=\begin{pmatrix} 1&2&3&4\\ 4&3&2&1 \end{pmatrix} \\ D=\begin{pmatrix} 1&2&3&4\\ 3&2&1&4 \end{pmatrix} \\ D'=\begin{pmatrix} 1&2&3&4\\ 1&4&3&2 \end{pmatrix} \end{matrix} \\\hline \end{array} $$ We now prove that each function above is an automorphism of $\mathcal{G}$. Each of the above is clearly a permutation of $V$. To verify that these are all automorphisms of $\mathcal{G}$, we must show for each permutation $\sigma$ above that $\{v_1,v_2\}$ is an edge if and only if $\{\sigma(v_1),\sigma(v_2)\}$ is an edge. The table below shows the computation for $\sigma = R_{90}$.

$$ \begin{array}{c|c} \{v_1,v_2\} & \{R_{90}(v_1),R_{90}(v_2)\}\\ \hline \{ 1,2\} & \{ 2,3\} \\ \{ 2,3\} & \{ 3,4\} \\ \{ 3,4\} & \{ 4,1\} \\ \{ 4,1\} & \{ 1,2\} \end{array} $$ Notice that each edge on the left appears exactly once on the right, which gives the required condition. Checking the other 7 is similar. Thus, we see $ \{R_0,R_{90},R_{180},R_{270},H,V,D,D'\}\subseteq \text{Aut}(\mathcal{G})$.

We claim that the list above gives all of the automorphisms of $\mathcal{G}$. Recall that the total number of automorphism is determined by the number of permutations of the set of vertices of $\mathcal{G}$ that map the set of edges of $\mathcal{G}$ onto $\mathcal{G}$. Let's count the number of automorphisms. Let $\sigma\in \text{Aut}(G)$. We know that $\sigma(1)\in \{1,2,3,4\}$, so there are 4 options for $\sigma(1)$. Since $\{\sigma(1),\sigma(2)\}$ is an edge, and $\sigma(1)$ appears in exactly two edges, we know that there are two options for $\sigma(2)$. This leaves one option for $\sigma(3)$ and $\sigma(4)$, as $\{\sigma(1),\sigma(4)\}$ and $\{\sigma(2),\sigma(3)\}$ must be edges. By the counting principle, this gives $4\cdot 2\cdot 1\cdot = 8$ possible options for $\sigma$. This proves that $\text{Aut}(\mathcal{G})= \{R_0,R_{90},R_{180},R_{270},H,V,D,D'\}$.

$\blacklozenge$

Tags
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.