Can someone give me some help with this problem:
How do I find the automorphism group of the complete binary rooted tree of height $3$ ($15$ vertices)?
when an automorphism $F$ on a graph $G=(V,E)$ is defined as follows:
$\{v,u\}$ is an edge in $E$ iff $\{F(v),F(u)\}$ is an edge in $F(E)$.
I tried to start counting the permutations, but it seems there is a different and better way to approach the problem.
Best Answer
Let $G_n$ denote the automorphism group of the complete binary rooted tree of height $n$. So, $G_1 \cong C_2$, the cyclic group of order $2$.
What about height $2$? You have automorphisms switching one pair of leaves on the left and the other pair on the right (in the usual planar picture of the rooted tree). Call these $a_1$ and $a_2$. Together they generate a subgroup of $G_2$ that is isomorphic to $C_2 \times C_2$, the Klein $4$ group. There is an additional automorphism generator, say $b$ that exchanges the left and right branches at the root. $G_2 \cong \langle a_1, a_2, b \rangle$. In fact the subgroup $\langle a_1, a_2 \rangle$ is normal in $G_2$, and $$ G_2 \cong (C_2 \times C_2) \rtimes C_2. $$ This construction is called a wreath product and can be written $$ C_2 \wr C_2. $$
Now, for height $3$ (and beyond), we iterate the construction. There are two isomorphic copies of $G_2$ in $G_3$ generated by the subtrees on either side of the root. The direct product of these two generate a normal subgroup inside of $G_3$, permuted by one additional generator at the root. So, $$ \begin{align} G_3 &\cong (G_2 \times G_2) \rtimes C_2 \\ &\cong \bigg( \big( (C_2 \times C_2) \rtimes C_2 \big) \times \big( (C_2 \times C_2) \rtimes C_2 \big) \bigg) \rtimes C_2, \end{align} $$ a group of order $2^7 = 128$, generated by $7$ involutions.
In other words, $G_3$ is an iterated wreath product: $$ G_3 \cong G_2 \wr C_2 \cong \big( C_2 \wr C_2 \big) \wr C_2. $$
Beyond $n = 3$, we have the recursive formula $$ G_{n + 1} \cong G_n \wr C_2 \cong \big( G_n \times G_n \big) \rtimes C_2, $$ which gives the recurrence relation for the orders of the automorphism groups: $$ \big| G_{n + 1} \big| = 2\big| G_n \big|^2. $$ Together with the base case $\big| G_1 \big| = 2$, the can be solved to show that $$ \big| G_n \big| = 2^{2^n - 1}. $$