My question is triggered by my confusion with the notation $\Psi$ in Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al.

The notation $\Psi$ was first used expressing general finite group while referring to Frucht’s Theorem on page 1. On page 2, Theorem 2 takes the special case where $\Psi$ is the subgroup of automorphism group of trees. The notation is $\Psi \in Aut(TREE)$ instead of $\Psi \le Aut(TREE)$ but I still consider the authors wanted to mean subgroups.

In Theorem 3, it is said that

$\Psi_i$ is a direct product of symmetric, cyclic and dihedral groups

It is not obvious whether $\Psi \in Aut(TREE)$ is still true.

From On automorphism groups of networks by MacArthur, I understand due to Polya that

automorphism groups of trees belong to the class of permutation groups which contains the symmetric groups and is closed under taking direct and wreath products.

MacArthur didn't mention cyclic and dihedral groups as Klavik did.

My question:

Should I still assume that $\Psi \in Aut(TREE)$ still held in the Theorem 3 of Klavik's paper?


You've misunderstood the notation. Refer to Definition 1: $\text{Aut}(TREE)$ is being used by the authors to denote the set of isomorphism classes of automorphism groups of (presumably finite) trees. So the notation $\Psi \in \text{Aut}(TREE)$ means that $\Psi$ is the full automorphism group of a particular tree. In fact Theorem 2 is just a restatement of the fact you quote from Polya.

You've also misunderstood Theorem 3, which is not about automorphisms of trees at all.

The answer to the question in your title is clearly no: since symmetric groups appear as automorphism groups of trees, every finite group is a subgroup of an automorphism group of a tree.

  • $\begingroup$ thanks. I understand that when $i \ne j$, $\Psi_i$ and $\Psi_j$ are the automorphism groups of two different trees. I agree that Theorem 3 is not about the automorphism group of tree but it mentions that $Ψ_i$ is a direct product of symmetric, cyclic and dihedral groups. So, if the answer to my question is no, why it says so? $\endgroup$ – Omar Shehab Jan 28 '16 at 5:10
  • $\begingroup$ @Omar: I don't understand your question. Theorem 3 describes an inductive characterization of automorphism groups of connected planar graphs. Each step of the induction involves a group $\Psi_i$ (not the automorphism group of a tree) which is a direct product of symmetric, cyclic, and dihedral groups. $\endgroup$ – Qiaochu Yuan Jan 28 '16 at 5:12
  • $\begingroup$ Do you suggest that the assumption $\Psi \in Aut(TREE)$ is not applicable for $\Psi_i$'s of Theorem 3? $\endgroup$ – Omar Shehab Jan 28 '16 at 5:14
  • 1
    $\begingroup$ Yes, that's what I'm saying. In that theorem $\Psi$ is just a group. I assume the point of this notation is that the authors want to reserve $G$ for graphs. $\endgroup$ – Qiaochu Yuan Jan 28 '16 at 5:15

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.