Frucht's theorem

The Frucht graph, a 3-regular graph whose automorphism group realizes the trivial group.

Frucht's theorem is a theorem in algebraic graph theory conjectured by Dénes Kőnig in 1936 and proved by Robert Frucht in 1939. It states that every finite group is the group of symmetries of a finite undirected graph. More strongly, for any finite group G there exist infinitely many non-isomorphic simple connected graphs such that the automorphism group of each of them is isomorphic to G.

Proof idea

The main idea of the proof is to observe that the Cayley graph of G, with the addition of colors and orientations on its edges to distinguish the generators of G from each other, has the desired automorphism group. Therefore, if each of these edges is replaced by an appropriate subgraph, such that each replacement subgraph is itself asymmetric and two replacements are isomorphic if and only if they replace edges of the same color, then the undirected graph created by performing these replacements will also have G as its symmetry group.[1]

Graph size

With three exceptions – the cyclic groups of orders 3, 4, and 5 – every group can be represented as the symmetries of a graph whose vertices have only two orbits. Therefore, the number of vertices in the graph is at most twice the order of the group. With a larger set of exceptions, most groups can be represented as the symmetries of a vertex-transitive graph, with a number of vertices equal to the order of the group.[2]

Special families of graphs

There are stronger versions of Frucht's theorem that show that certain restricted families of graphs still contain enough graphs to realize any symmetry group. Frucht (1949) proved that in fact countably many 3-regular graphs with the desired property exist; for instance, the Frucht graph, a 3-regular graph with 12 vertices and 18 edges, has no nontrivial symmetries, providing a realization of this type for the trivial group. Sabidussi (1957) showed that any group can be realized as the symmetry groups of countably many distinct k-regular graphs, k-vertex-connected graphs, or k-chromatic graphs, for all positive integer values k (with k ≥ 3 for regular graphs and k ≥ 2 for k-chromatic graphs). From the facts that every graph can be reconstructed from the containment partial order of its edges and vertices, that every finite partial order is equivalent by Birkhoff's representation theorem to a finite distributive lattice, it follows that every finite group can be realized as the symmetries of a distributive lattice, and of the graph of the lattice, a median graph.[1] It is possible to realize every finite group as the group of symmetries of a strongly regular graph.[3] Every finite group can also be realized as the symmetries of a graph with distinguishing number two: one can (improperly) color the graph with two colors so that none of the symmetries of the graph preserve the coloring.[4]

However, some important classes of graphs are incapable of realizing all groups as their symmetries. Camille Jordan characterized the symmetry groups of trees as being the smallest set of finite groups containing the trivial group and closed under direct products with each other and wreath products with symmetric groups;[5] in particular, the cyclic group of order three is not the symmetry group of a tree. Planar graphs are also not capable of realizing all groups as their symmetries; for instance, the only finite simple groups that are symmetries of planar graphs are the cyclic groups and the alternating group A5.[6] More generally, every minor-closed graph family is incapable of representing all finite groups by the symmetries of its graphs.[7] László Babai conjectures, more strongly, that each minor-closed family can represent only finitely many non-cyclic finite simple groups.[8]

Infinite groups and graphs

For infinite graphs, Izbicki (1959) extended each of these results to show that there were uncountably many graphs realizing any symmetry group. Finally, de Groot (1959) and Sabidussi (1960) independently proved that any group (dropping the assumption that the group be finite) could be realized as the group of symmetries of an infinite graph.

Notes

  1. 1 2 Babai (1995), discussion following Theorem 4.1.
  2. ↑ Babai (1995), Section 4.3.
  3. ↑ Babai (1995), Theorem 4.3.
  4. ↑ Albertson, Michael O.; Collins, Karen L. (1996), "Symmetry breaking in graphs", Electronic Journal of Combinatorics, 3 (1): R18, MR 1394549.
  5. ↑ Babai (1995), Proposition 1.15. Babai dates Jordan's result to 1869, but includes only an 1895 paper of Jordan in his bibliography.
  6. ↑ Babai (1995), discussion following Theorem 1.17.
  7. ↑ Babai (1995), Theorem 4.5.
  8. ↑ Babai (1995), discussion following Theorem 4.5.

References

This article is issued from Wikipedia - version of the 3/15/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.