# Can every permutation group be realized as the automorphism group of a graph (acting on a subset of the vertices)?

By Frucht's theorem, every finite group can be realized as the automorphism group of a finite undirected graph. Because a permutation group is a finite group, it is clear that every permutation group be realized as the automorphism group of a graph. However, a permutation group acts on its underlying set, and I also want to realize this group action on a subset of the vertices of the graph.

An equivalent description of what I want is that I'm given a set of vertices and a permutation group acting on those vertices, and I want to construct a graph around those vertices such that the automorphism group of the graph realizes the given permutation group on the given set of vertices.

If the permutation group acts $2$-transitively on the underlying set, then the graph would have to be discrete or complete, in which case the full automorphism group of the graph would be be the symmetric group. This shows that you can't achieve your goal for any $2$-transitive group other than the symmetric group. (E.g., $A_n$ is a problem.)

EDIT (8-23-15): OK, I see from your comment that I did not understand the question. If I now understand the question, then I can say that it has a positive answer.

I am assuming that the question is this: Let $(X,P)$ be a finite permutation group. Is it possible to find a graph $G=(V,E)$ with $X\subseteq V$ such that every automorphism of $G$ maps $X$ into itself, and the restriction of $\textrm{Aut}(G)$ to $X$ is just $P$?

Here is a construction. First, find graph $H=(W,F)$ such that (i) $\textrm{Aut}(H)\cong P$ and (ii) $\textrm{Aut}(H)$ has a regular orbit, say $O$. This is possible. (Frucht's argument produces such an $H$.) Now we build a first approximation to the desired graph on the disjoint union $X\cup W$ of the set $X$ and the vertex set of $H$. Observe that $P$ has an action on this union, since it acts on each summand.

The edge set of our first approximation will include only the edges from $F$ (the edge set of $H$), which connect vertices within $W$ to other vertices within $W$, together with some new edges connecting $W$ to $X$. The edges from $F$ will not be directed or colored, but the new edges will be directed and colored.

The new edges are selected as follows: pick an element $w\in O$ from our fixed regular orbit of $H$, and pick $x_1,\ldots, x_k\in X$ from each of the orbits of $P$ on $X$. For each $\pi\in P$ add directed edges from $\pi(w)$ to $\pi(x_1),\ldots,\pi(x_k)$. Color the edge from $\pi(w)$ to $\pi(x_i)$ with the label $i$. It is not hard to see that the color and direction preserving automorphisms of the resulting graph are exactly those induced by elements of $P$.

Now we refine our first approximation to obtain the desired graph. Use Frucht's trick of replacing colored edges with rigid graph pieces, so that graph automorphisms of the enlarged graph correspond to directed, colored graph automorphisms of the original graph. This construction does not change the sets $W$ or $X$, only adds new vertices between them. With these choices, $X$ is invariant under all automorphisms, and restriction to $X$ is an isomorphism of the automorphism group onto $P$.

• The subgraph formed by the given vertices would have to be discrete or complete. But we cannot conclude the same for the graph around those given vertices, so it could still be possible to achieve the goal. – Thomas Klimpel Aug 23 '15 at 19:40
• Here's an extremely similar construction that no longer merits its own answer. As usual I'll state the labelled version. Start with the full Cayley graph $\Gamma$ of $P$; $P$ acts on $V(\Gamma) = P$ by $\pi(\rho) = \pi \rho$. Form the complete bipartite graph between $P$ and $X$. The group action has to be encoded somewhere, so label each edge $(\pi, x)$ by $\pi^{-1}(x)$. I think that this works as required. It would be very interesting to see a construction that does not essentially pass through the Cayley graph. – Ben Barber Aug 23 '15 at 21:39

FYI, this result exists in the literature. The two citations I know of are:

L. Babai. Representation of permutation groups by graphs. In Combinatorial theory and its applications, I (Proc. Colloq., Balatonfured, 1969), pages 55–80. North- Holland, Amsterdam, 1970.

and

I. Z. Bouwer. Section graphs for finite permutation groups. J. Combinatorial Theory, 6:378–386, 1969.