What is the minimal number of vertices of a graph $\Gamma$ such that $\Gamma$ has automorphism group $PSL(2,7)$, the finite simple group of order $168$? Better yet, what is this graph?
Basically I am asking this question: Smallest graph with automorphism group the quaternion $8$-group, $Q_8$.
I thought maybe the Fano plane (https://en.wikipedia.org/wiki/Fano_plane) thought of as a graph would work but I have no idea how to prove that. Worse yet, when I enter that as a graph into Mathematica, the automorphism group only has order 6, so maybe I am misunderstanding something? Sorry, I am a bit new to graph theory.
For a $14$-vertex construction, start with the Heawood graph; this is a bipartite graph whose automorphism group is $PGL_2(7)$, so it's twice as big as we want. The Heawood graph is bipartite, and the extra factor of $2$ comes from being able to swap the two parts of the bipartition. So if we add a clique joining all $7$ vertices on one side of the bipartition, we distinguish it from the other side, and get a graph with automorphism group only $PSL_2(7)$.
(On the left, you see the Heawood graph; on the right, the new graph we constructed, with the edges of the Heawood graph in red and the clique edges in blue.)
From the point of view of the Fano plane, this new graph has the following construction:
Every automorphism of the Fano plane can be applied to this graph as well; the edges between all the point-vertices prevent us from getting automorphisms that take the dual of the Fano plane (swapping points and lines).
Here is a proof that there is no smaller graph.
We need at least $7$ vertices, and I checked all $1044$ $7$-vertex graphs to see that exactly $7$ vertices is impossible. Now suppose that $G$ is a graph with some number of vertices between $8$ and $13$.
Let $\sigma$ be an automorphism of $G$ of order $7$. (There should be $48$ of these.) For every vertex $v$, $\sigma^7(v)=v$, which means that either $\sigma(v)=v$ or else $\{v, \sigma(v), \dots, \sigma^6(v)\}$ is a $7$-vertex orbit. Since $\sigma$ shouldn't fix every vertex, and there is not room for two such orbits, it has exactly one $7$-vertex orbit, $A$. Also, let $\tau$ be an automorphism of order $7$ that's not one of $\sigma, \sigma^2, \dots, \sigma^6$; it has exactly one $7$-vertex orbit too, call it $B$.
Note that if there is any vertex $v \notin A \cup B$, $v$ should have the same adjacency relationship to every vertex in $A \cup B$ (adjacent to all of them or none of them), because edges and non-edges are preserved by applying $\sigma$ and $\tau$, which fix $v$ and act transitively on $A \cup B$. A consequence of this is that if $H = G[A \cup B]$ (the subgraph induced by $A \cup B$) then any automorphism of $H$ extends to an automorphism of $G$ by fixing the vertices outside $A \cup B$.
Case 1. $A=B$.
Then $\sigma$ and $\tau$ generate a subgroup of the automorphism group that fixes vertices outside $A$. Notably, every subgroup of $S_7$ generated by two $7$-cycles is either a cyclic group of order $7$, the group $PSL(2,7)$ we want, or all of $S_7$. The first case is ruled out by assumption: $\sigma$ already generates a cyclic group of order $7$, and $\tau$ is not in it. The third case gives too many automorphisms. So it must be the case that $\sigma$ and $\tau$ generate the entire automorphism group of the graph $G$.
As before, let $H$ be the induced graph $G[A]$. Every automorphism of $G$ fixes $A$, so it is an automorphism of $H$, and every automorphism of $H$ extends to an automorphism of $G$. Therefore $H$ is a $7$-vertex graph with automorphism group $PSL(2,7)$, which we have already ruled out.
Case 2. $A \ne B$.
Pick vertices $v \in A \setminus B$ and $w \in B \setminus A$. Without loss of generality (taking the complement graph if necessary), edge $vw$ exists. By applying $\tau$ repeatedly, we see that $v$ must be adjacent to each vertex in $B$. Applying $\sigma$ first to map $v$ to any other vertex in $A \setminus B$, we see that all edges between $A \setminus B$ and $B$ are present.
In particular, within $A$, there is a complete bipartite graph between $A \setminus B$ and $A \cup B$; applying $\sigma$ to this repeatedly, we get all edges between vertices in $A$. Similarly, we get all edges between vertices in $B$, and at this point, all edges between vertices in $A \cup B$ must exist.
But now, the induced subgraph $H = G[A \cup B]$ is a complete graph on at least $8$ vertices, so it has an automorphism group of at least $8!$ elements, all of which extend to automorphisms of $G$; that's too many to get the group $PSL(2,7)$ we wanted.