Welcome to MathOverflow

Question

2

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?

flag	asked Feb 8 at 11:00 Jérôme JEAN-CHARLES 608●7●15

Brendan McKay · Answer 1 · 2013-02-08 13:46:04Z UTC

7

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?

edited Feb 8 at 13:46

answered Feb 8 at 11:42

Brendan McKay
9,111●1●13●33

	I think this indeed a theorem of Jordan. – Olivier Feb 8 at 12:10
	No non-trivial group of odd order is an automorphism group of a tree. – Chris Godsil Feb 8 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 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 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 at 19:02

Which finite group is not the automorphism group of some rooted finite trees

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.