Automorphism group for a graph

132 Views Asked by At

I don't understand some basic definitions in the setup for the following problem from Springer's Algebraic Combinatorics', and would love some clarification:

"For a simple graph Γ with vertex set V , we can define an automorphism of Γ to be a bijection ϕ: V → V such that u and v are adjacent if and only if ϕ(u) and ϕ(v) are adjacent. The automorphisms form a group under composition, called the automorphism group, Aut(Γ) of Γ.

Let Γ be a simple graph of 7 elements such that node 1 branches to nodes 2 and 3, and each of those branch to nodes 4 and 5 and nodes 6 and 7 respectively.

Let G be the automorphism group of Γ, so G has order eight."

My question (which I think will enable me to solve the actual problems relating to this setup) is, what are these 8 elements in G? I must be missing something basic, because I don't understand what one of these elements might look like (besides the identity of course, which would leave the graph alone). If you swapped nodes 6 and 7 (2 leaf nodes that share a parent) for example, you would get the same graph as before by any reasonable definition of a simple graph, right? I think I'm just missing something really basic here and am lost, so any help would be appreciated. (For the full problem, you can head to problem 7.1 on web pdf page #18 at http://math.mit.edu/~rstan/exer.pdf)

Thank you!

3

There are 3 best solutions below

0
On

If you swap $6$ and $7$, you get "the same" graph, to be sure, but that just means that this is an automorphism! If your bijection $\phi$ leaves all vertices intact except it swaps $6$ with $7$, then it's certainly not an identity function on $V$, and yet clearly it's an automorphism according to the definition of an automorphism.

Think of a bijection of $V$ as a relabelling of vertices, and an automorphism is a way to relabel vertices so that edge relationships stay the same. Your problem was that you intuitively thought of relabelling that "doesn't change anything" as identity. But it isn't; it still moves vertices around; it's just an automorphism.

So your automorphisms are:

  • identity
  • swap $4$ with $5$
  • swap $6$ with $7$
  • product of the previous two
  • swap the subtree under $2$ with the subtree under $3$
  • products of the previous with the 3 before it.
1
On

Well, your observation just produced one of the elements of the automorphism group: swapping 6 and 7. Similarly, you can swap 4 and 5, or you can swap nothing, or you can swap 6-7 and 4-5 simultaneously. This gives you 4 elements of the automorphism group.

So far, you have left the parent nodes alone. Now you can swap those, too. Swapping 2-3, however, requires transporting somehow the children nodes to carry edges to edges. You can do this anyway you like, for instance, 2-3, 4-47, 5-6. This is another element of the automorphism group.

Now you can follow this transformation with one of the previous 4 swaps.

This gives us: 4 swaps where 2-3 are not flipped, and 4 swaps with 2-3 flipped, for a total of 8 elements.

Then you have to show that no other bijection gives you an automorphism and you can do this by arguing: if $f$ is an automorphism, the degree of each edge is preserved.

0
On

There are three internal nodes; at each one of these, you can swap the left and right subtrees. That is, each of the three maps $(45)$, $(67)$, $(23)(46)(57)$ is an automorphism. These three guys generate a group of order eight.

It's not hard to see this is the whole automorphism group; $1$ must map to itself since it's the only midpoint of a $4$-long path.