Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

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?

share|cite|improve this question

1 Answer 1

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?

share|cite|improve this answer
I think this indeed a theorem of Jordan. –  Olivier Feb 8 '13 at 12:10
No non-trivial group of odd order is an automorphism group of a tree. –  Chris Godsil Feb 8 '13 at 12:46
How funny that my context is in fact graph isomorphism and Brendan is the first to answer this. Mysterious or funny ? –  Jérôme JEAN-CHARLES Feb 8 '13 at 12:51
Thank you very much , there is still an aspect of "density". Do we loose kind of "half" when restricting to (FTAG) FiniteTree-Automorphism -Groups ? –  Jérôme JEAN-CHARLES Feb 8 '13 at 14:21
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. –  David Speyer Feb 8 '13 at 19:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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