Realizing groups as automorphism groups of graphs. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:17:04Z http://mathoverflow.net/feeds/question/37356 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37356/realizing-groups-as-automorphism-groups-of-graphs Realizing groups as automorphism groups of graphs. Stefan Geschke 2010-09-01T08:19:10Z 2010-09-01T17:46:20Z <p>Frucht showed that every finite group is the automorphism group of a finite graph. The paper is <a href="http://www.numdam.org/item?id=CM_1939__6__239_0" rel="nofollow">here</a>.<br> 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.</p> <p>This argument seems to carry over to the countably infinite case.<br> Does anybody know a reference for this?</p> <p>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.</p> http://mathoverflow.net/questions/37356/realizing-groups-as-automorphism-groups-of-graphs/37357#37357 Answer by Tony Huynh for Realizing groups as automorphism groups of graphs. Tony Huynh 2010-09-01T08:30:27Z 2010-09-01T08:35:37Z <p>According to the <a href="http://en.wikipedia.org/wiki/Frucht%27s%5Ftheorem" rel="nofollow">wikipedia page</a>, <em>every</em> group is indeed the automorphism group of some graph. This was proven independently in </p> <p>de Groot, J. (1959), <em>Groups represented by homeomorphism groups</em>, Mathematische Annalen 138 </p> <p>and </p> <p>Sabidussi, Gert (1960), <em>Graphs with given infinite group</em>, Monatshefte für Mathematik 64: 64–67.</p> http://mathoverflow.net/questions/37356/realizing-groups-as-automorphism-groups-of-graphs/37400#37400 Answer by Christian Rosendal for Realizing groups as automorphism groups of graphs. Christian Rosendal 2010-09-01T16:48:12Z 2010-09-01T17:46:20Z <p>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:</p> <p>(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.</p> <p>(2) The abstract group of increasing homeomorphisms of $\mathbb R$, ${\rm Homeo}_+(\mathbb R)$, has no non-trivial actions on a set of size $&lt;2^{\aleph_0}$. So in particular, it cannot be represented as the automorphism group of a graph with less than continuum many vertices.</p>