27
$\begingroup$

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.

$\endgroup$

2 Answers 2

22
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks. I somehow missed that wikipedia page. I only found the one with the Frucht graph and related paper. $\endgroup$ Sep 1, 2010 at 8:37
  • $\begingroup$ 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. $\endgroup$ Sep 1, 2010 at 8:53
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Sep 1, 2010 at 9:10
14
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ Hi Christian! Nice to see you here. $\endgroup$ Sep 1, 2010 at 17:04
  • 1
    $\begingroup$ Hi Christian! Nice to see you! I fixed a small typo in your post. $\endgroup$ Sep 1, 2010 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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