most recent 30 from http://mathoverflow.net 2013-05-22T04:15:00Z http://mathoverflow.net/feeds/question/37383 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37383/groups-as-automorphism-groups-of-small-graphs-and-the-number-of-rigid-graphs-of-a Stefan Geschke 2010-09-01T14:34:16Z 2010-09-01T17:38:47Z

<p>In a recent question of mine I asked whether every infinite group is (isomorphic to) the automorphism group of a graph. The finite case was done by Frucht in 1939. </p> <p>The first answer to this question pointed out two papers answering my original question, one by <a href="http://www.springerlink.com/content/qn32208134273016/" rel="nofollow">Sabidussi</a> and one by <a href="http://www.springerlink.com/content/w5446363757612w8/" rel="nofollow">de Groot</a>.</p> <p>Reading the 3-page paper by Sabidussi I thought "Wow, these graphs are huge": Sabidussi realizes a group of size $\kappa$ as the automorphism group of a graph of size $\aleph_\kappa$. </p> <p>Indeed, de Groot in his paper notes that every countable group is the automorphism group of a countable graph, every group of size $\leq 2^{\aleph_0}$ is the automorphism group of a graph of size $\leq 2^{\aleph_0}$, and every group of size $\kappa$ is the the automorphism group of a graph of size $\leq 2^{\kappa}$.</p> <p>But in general, he doesn't know how large a graph is needed to realize a given group.</p> <p>Has this issue been resolved? Is there a reason why for a given infinite group $G$ there shouldn't be a graph of size $|G|$ whose automorphism group is isomorphic to $G$?</p> <p>As I said in my original question, by Frucht's construction (and the constructions of de Groot and Sabidussi) this is related to the question whether there are $\kappa$ many non-isomorphic rigid graphs of size $\kappa$, where a graph is rigid if the identity is the only automorphism.<br> Is this known? I would guess that there are $2^\kappa$ pairwise non-isomorphic rigid graphs of infinite size $\kappa$, but maybe I am wrong.</p>

http://mathoverflow.net/questions/37383/groups-as-automorphism-groups-of-small-graphs-and-the-number-of-rigid-graphs-of-a/37390#37390 David Eppstein 2010-09-01T15:29:45Z 2010-09-01T15:29:45Z

<p>See <a href="http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps" rel="nofollow">Babai, László (1995), "Automorphism groups, isomorphism, reconstruction", in Graham, Ronald L.; Grötschel, Martin; Lovász, László, Handbook of Combinatorics, I, North-Holland, pp. 1447–1540.</a>, section 4.3. In the finite case, he states that with three exceptions (the cyclic groups C3, C4, and C5) there is a graph that realizes any symmetry group and has only two orbits of vertices. There are infinitely many groups that require two orbits but "most" groups can be realized with only one. I realize you're asking about infinite groups rather than finite groups but maybe the same at-most-two-orbits bound carries over?</p>

http://mathoverflow.net/questions/37383/groups-as-automorphism-groups-of-small-graphs-and-the-number-of-rigid-graphs-of-a/37402#37402 Simon Thomas 2010-09-01T17:02:35Z 2010-09-01T17:38:47Z

<p>It is well-known that every infinite group $G$ can be realized as the automorphism group of a graph of size $|G|$. It is also well-known that for each infinite cardinal $\kappa$, there are $2^{\kappa}$ nonisomorphic rigid graphs of size $\kappa$. For example, both results are easily extracted from Section 4.2 of the following unpublished book:</p> <p><a href="http://www.math.rutgers.edu/~sthomas/book.ps" rel="nofollow">http://www.math.rutgers.edu/~sthomas/book.ps</a></p>