geometric-group-theorygraph theorygroup-theory
Let $G$ be a finite group and $S$ a generating set of $G$. We can draw the Cayley graph $C(G,S)$ by putting each element of $G$ as a vertex, and drawing an edge between two elements $g$, $h\in G$ iff $g^{-1} h \in S$.
Choose $x\in G$. Note that the map $g \mapsto xg$ is a graph automorphism of $C(G,S)$. This allows us to embed $G \le \text{Aut}(C(G,S))$.
My question is: when is it in fact the case that $G = \text{Aut}(C(G,S))$? Is there a nice criterion to determine this?
Edit: 16 vertices is indeed the smallest possible size for such a graph (see the proof below).
Here's an example of a graph with 16 vertices whose automorphism group is $Q_8$. As we will show, the automorphisms of the graph preserve the colors and arrows:
The symmetry of this graph is similar to the symmetry of the Cayley graph of $Q_8$ shown in the question above. Here's an argument that it's possible to recover the colors and arrows from the structure of the graph itself:
Cyan vertices have degree 7, while yellow vertices have degree 5.
Black edges connect pairs of yellow vertices.
Green edges connect vertices of different colors and do not share triangles with black edges.
Purple edges connect cyan vertices and are involved in triangles with green edges.
Red edges connect vertices of different colors and are involved in triangles with green and purple edges.
Blue edges connect vertices of different colors and are neither red nor green.
Cyan edges connect cyan vertices and are not purple.
Each black edge is involved in exactly one black-red-blue triangle, and the arrow points from the vertex opposite the red edge to the vertex opposite the blue edge.
Using the colors and arrows, it's easy to prove that any automorphism of this graph that fixes a vertex must fix all 16 vertices, so there are at most eight automorphisms. It's easy to check that there are in fact eight automorphisms, which form a copy of $Q_8$.
Incidentally, Babai constructs a 16-vertex graph for $Q_8$ in his paper "On the minimum order of graphs with given group" with 52 edges. The graph above is a slight improvement on this, having the same number of vertices but only 48 edges. Though 16 is the minimum possible number of vertices, it would be interesting to know whether there's a 16-vertex graph with fewer than 48 edges that has symmetry group $Q_8$.
Edit: 16 vertices is indeed the minimum possible. Indeed, any graph whose automorphism group is $Q_8$ must have at least two orbits of size $8$.
To see this, observe first that any faithful action of $Q_8$ on a graph must have at least one orbit of size $8$, since otherwise the action factors through $Q/\{\pm 1\}$.
Now, suppose we have a faithful action of $Q_8$ on a graph $G$, and suppose that $G$ has just one orbit of size $8$. Let $v$ be a vertex in this orbit. I claim that switching $v$ with $-1v$ is an automorphism of $G$. This automorphism is not in $Q_8$, since the action of $Q_8$ on the orbit of size $8$ is the left regular action, so it follows that the automorphism group of $G$ is larger than $Q_8$.
To prove that switching $v$ and $-1v$ is an automorphism of $G$, observe that:
If $w$ is any vertex not in the orbit of size $8$, then the stabilizer of $w$ is a proper subgroup of $Q_8$, so $-1w = w$. Thus, there is an edge from $v$ to $w$ if and only if there is an edge from $-1v$ to $w$.
If there is an edge from $v$ to $iv$, then its image under $i$ is an edge from $iv$ to $-1v$. Thus $v$ is connected by an edge to $iv$ if and only if $-1v$ is connected by an edge to $iv$. The same holds for $-iv$, $\pm j v$, and $\pm k v$.
This proves the claim, and therefore 16 is the smallest possible size.
Best Answer
In general, there is no nice characterization of the connection sets $C$ such that the Cayley graph $\mathrm{Aut}(X(G,C)) \cong G$. (Such a graph is called a graphical regular representation for $G$, abbreviated (thankfully) to GRR.)
It is clearly necessary that the connection set generates the group.
If $G$ admits a non-identity automorphism that, for each element of $G$, either fixes it or maps it to its inverse, then the stabilizer of a vertex for any Cayley graph contains an element of order two. This rules out GRRs for abelian groups with exponent greater than two, and groups like the quaternion group (so-called generalized dicyclic groups).
If a group is not abelian with exponent greater than three, not generalized dicyclic, and has order at least 32 then it does have a GRR. (This is not trivial and rests on the work of a long list of people.)
If $G$ is nilpotent and not abelian, then almost all Cayley graphs for $G$ are GGRs (Babai and me). I proved (using some nontrivial group theory) that if $G$ is a $p$-group with no homomorphism on the the wreath product of $\mathbb{Z}_p$ by $\mathbb{Z}$, and $C$ is a connection set that is not fixed by any non-identity automorphism of $G$, then $X(G,C)$ is a GRR. So in this one case we do have a characterization of the connection sets that result in GRRs.