Realizing groups as automorphism groups of graphs. - MathOverflow

Realizing groups as automorphism groups of graphs.

2010-09-01T08:19:10Z

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.

Answer by Tony Huynh for Realizing groups as automorphism groups of graphs.

2010-09-01T08:30:27Z

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.

Answer by Christian Rosendal for Realizing groups as automorphism groups of graphs.

2010-09-01T16:48:12Z

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.