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

Frucht showed that every finite group is the automorphism group of a finite graph. The paper is here.
The argument basically is that a group is the automorphism group of its (colored) Cayley graph and that the colors of edge in the Cayley graph can be coded into an uncolored graph that has the same automorphism group.

This argument seems to carry over to the countably infinite case.
Does anybody know a reference for this?

In the uncountable, is it true that every group is the automorphism group of a graph? (Reference?) It seems like one has to code ordinals into rigid graphs in order to code the uncountably many colors of the Cayley graph.

share|improve this question

2 Answers 2

up vote 11 down vote accepted

According to the wikipedia page, every group is indeed the automorphism group of some graph. This was proven independently in

de Groot, J. (1959), Groups represented by homeomorphism groups, Mathematische Annalen 138

and

Sabidussi, Gert (1960), Graphs with given infinite group, Monatshefte für Mathematik 64: 64–67.

share|improve this answer
    
Thanks. I somehow missed that wikipedia page. I only found the one with the Frucht graph and related paper. –  Stefan Geschke Sep 1 '10 at 8:37
    
From de Groot's paper you can see that this argument you described goes pretty far, for graphs, topological spaces etc. Coding arbitrary number of colors is done through some rigid spaces with no automorphisms. –  Gjergji Zaimi Sep 1 '10 at 8:53
    
Yes, Stefan certainly had the right idea in mind. I'll just remark that Sabidussi's paper meets my requirements for recreational math reading; it's only three pages long. –  Tony Huynh Sep 1 '10 at 9:10

In the topological setting or if you want to relate the size of the graph to the size of the group, there are two relevant results:

(1) Any closed subgroup of $S_\infty$, i.e., of the group of all (not just finitary) permutations of $\mathbb N$, is topologically isomorphic to the automorphism group of a countable graph.

(2) The abstract group of increasing homeomorphisms of $\mathbb R$, ${\rm Homeo}_+(\mathbb R)$, has no non-trivial actions on a set of size $<2^{\aleph_0}$. So in particular, it cannot be represented as the automorphism group of a graph with less than continuum many vertices.

share|improve this answer
1  
Hi Christian! Nice to see you here. –  Andres Caicedo Sep 1 '10 at 17:04
    
Hi Christian! Nice to see you! I fixed a small typo in your post. –  François G. Dorais Sep 1 '10 at 17:47
    
This is interesting, thank you. –  Stefan Geschke Sep 2 '10 at 8:52

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.