10
$\begingroup$

The question is as given in the title:

Which finite groups are not the automorphism group of some rooted finite tree?

A rephrasing could be: Is any finite group representable as the automorphism group of a finite tree? If not, what is typically unrepresentable?

In case of ambiguity: a homomorphism of finite rooted trees must preserved the root, and so does an isomorphism which is called an automorphism.

Context:
The motivation/spirit of the question is as follows. I make the isomorphism classes of finite graphs smaller by specifying a group acting on the graph's vertices, that is an isomorphism must now respect the group action (instead of the bigger $S(n)$ action). Do I lose something by restricting myself to tree automorphisms instead of considering the group action?

$\endgroup$

1 Answer 1

14
$\begingroup$

If I remember correctly, the automorphism groups of trees are those groups which you can make from symmetric groups by direct products and wreath products. This is rather few groups.

An example of a group not occurring would be a nontrivial group with no subgroup of index 2. All simple groups from $Z_3$ upwards, for example.

ADDED: An application of the constructive characterization is that a positive integer is the order of the group of a tree iff it is a product of factorials. So there are no odd numbers, only 2 and 6 as twice an odd number, etc.. Apparently these are called the Jordan-Polya numbers.

For homework, which groups have one of the allowed orders but still aren't groups of trees?

$\endgroup$
6
  • $\begingroup$ I think this indeed a theorem of Jordan. $\endgroup$
    – Olivier
    Feb 8, 2013 at 12:10
  • $\begingroup$ No non-trivial group of odd order is an automorphism group of a tree. $\endgroup$ Feb 8, 2013 at 12:46
  • $\begingroup$ How funny that my context is in fact graph isomorphism and Brendan is the first to answer this. Mysterious or funny ? $\endgroup$ Feb 8, 2013 at 12:51
  • $\begingroup$ Thank you very much , there is still an aspect of "density". Do we loose kind of "half" when restricting to (FTAG) FiniteTree-Automorphism -Groups ? $\endgroup$ Feb 8, 2013 at 14:21
  • 1
    $\begingroup$ The "made from symmetric groups by direct products and wreath products" criterion implies that every Jordan-Holder factor will be either $A_n$ (for some $n$), $\mathbb{Z}/2$ or $\mathbb{Z}/3$. It shouldn't be too hard to, for example, take the simple group of order $168$ and multiply it by some cyclic group in order to obey the conditions you have given. $\endgroup$ Feb 8, 2013 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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