Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The question is in the title, 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 :
An homomorphism of finite rooted trees must preserved the root, and so does an isomorphism which is called an automorphism.

Contexte :
The cause/spirit of the question is : I make the isomorphism class of finite graphs smaller by specifying a group acting on the graph's vertices, that is an isomorphism must respect the group action (instead of the bigger $S(n)$ action).
Do I loose something by restricting myself to trees automorphism instead of group?

share|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.