2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ One element of Aut($\Gamma$) is always the identity permutation (map each vertex in $V$ to itself), which plays the role of the identity element of this group. But you seem to have identified some of the nontrivial permutations that "preserve" the adjacency structure in $\Gamma$. $\endgroup$ – hardmath Oct 12 '15 at 0:32
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This makes sense! Thanks you $\endgroup$ – Veronica Soufre Oct 12 '15 at 4:23
1
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.