28
$\begingroup$

Frucht's Theorem states that for any finite group $G$ there is a finite (undirected) graph $\Gamma$ for which the automorphism group $\text{Aut}(\Gamma)$ of $\Gamma$ is isomorphic to $G$, and for many small groups $G$ it is not hard to construct a small graph $\Gamma$ whose automorphism group $\text{Aut}(\Gamma)$ is isomorphic to $G$.

For example, $\Bbb Z_1$, $\Bbb Z_2$, and $S_3$ are the automorphism groups of the complete graphs $K_1, K_2$, $K_3$, respectively, $\Bbb Z_2 \times \Bbb Z_2$ is the automorphism group of

enter image description here,

$\Bbb Z_3$ is the automorphism group of the $9$-vertex graph

enter image description here,

$\Bbb Z_4$ and $\Bbb Z_5$ are respectively the automorphism groups of the $12$- and $15$-vertex analogues of that graph given (informally) by replacing the central triangle with a square or pentagon, $\Bbb Z_6$ is the automorphism group of the $12$-vertex graph

enter image description here ,

and $\Bbb Z_7$, $\Bbb Z_8$, and $\Bbb Z_9$ are the respectively the automorphism groups of the $14$-, $16$-, and $18$-vertex analogues of that graph given by replacing the hexagons with heptagons, octagons, and nonagons.

This accounts for all groups of order $< 10$ (in fact, except for the example for $\Bbb Z_4$, these examples are all minimal w.r.t. vertex count, at least among connected graphs) except $\Bbb Z_2 \times \Bbb Z_2 \times \Bbb Z_2$, $\Bbb Z_3 \times \Bbb Z_3$, and the quaternion $8$-group, $Q_8$. One can modify without much fuss the above examples to produce graphs with automorphism groups the abelian groups in this list, but it is not so clear (to me) to see how to construct a reasonably small graph with automorphism group $Q_8$:

What is the minimal number of vertices of a graph $\Gamma$ for which $\text{Aut}(\Gamma) \cong Q_8$? What is an example of such a graph that achieves this minimum? Among such graphs, which has (have) the minimal number of edges?

We can given an upper bound for the vertex count: A theorem of Babai says for all groups $G \not\cong \Bbb Z_3, \Bbb Z_4, \Bbb Z_5$ there is a graph $\Gamma$ with $\text{Aut}(\Gamma) \cong G$ such that the action of $\text{Aut}(G)$ has only two orbits, and so in particular has vertex count $V(\Gamma)$ no larger than $2|G|$; thus, there is a graph $\Gamma$ with $\text{Aut}(\Gamma) \cong Q_8$ and $V(\Gamma) \leq 16$. (I expect that $16$ is also the minimum achievable.)

One can attempt to solve this by exploiting a constructive proof of Frucht's Theorem: Roughly, one starts with a Cayley graph of $G$ (which is directed and colored according to generator), which has automorphism group (of directed, colored graphs) $G$. Then, one replaces each edge with a suitable (undirected) graph, choosing a different replacement graph for each generator, to avoid introducing new symmetries.

It is not clear, however, that this approach can produce a graph with $\leq 16$ vertices and automorphism group $Q_8$. The simplest Cayley graph of $Q_8$ is

enter image description here,

but this already has $16$ edges, and it's hard to see how one could suitably replace them without added more than $8$ new vertices in total.

This answer, by the way, gives a graph with $32$ vertices with automorphism group $Q_8$ (acting with $4$ orbits on the graph):

enter image description here.

Incidentally, one can use the above approach to improve upon this result, i.e., construct a graph $\Gamma$ with $< 32$ vertices and automorphism group $Q_8$: Let $S(p, q)$ denote the graph with three vertices $a, b, c$, $p$ edges between $a$ and $b$, and $q$ edges between $b$ and $c$. Then, we can replace the red arrows in the above Cayley graph with $S(p, q)$ (appropriately oriented) and the green arrows with $S(p', q')$, where $p, q, p', q'$ are chosen to avoid introducing new automorphisms. Each replacement adds one vertex, so the resulting graph has $24$ vertices. (This graph is, however, not simple, and so is less than entirely satisfying.)

Babai, L., "On the minimum order of graphs with given group." Canad. Math. Bull., 17, pp. 467–470, 1974.

Frucht, R., "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compositio Mathematica (in German) 6, pp. 239–250, 1939.

$\endgroup$
17
$\begingroup$

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:

enter image description here

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:

  1. Cyan vertices have degree 7, while yellow vertices have degree 5.

  2. Black edges connect pairs of yellow vertices.

  3. Green edges connect vertices of different colors and do not share triangles with black edges.

  4. Purple edges connect cyan vertices and are involved in triangles with green edges.

  5. Red edges connect vertices of different colors and are involved in triangles with green and purple edges.

  6. Blue edges connect vertices of different colors and are neither red nor green.

  7. Cyan edges connect cyan vertices and are not purple.

  8. 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.

$\endgroup$
  • $\begingroup$ This is excellent, thank you for the detailed answer. I cannot find the graph you mention in Babai's "On the minimum order of graphs with given group"---perhaps I am missing something (but the paper is very short). $\endgroup$ – Travis Jun 9 '15 at 2:28
  • $\begingroup$ @Travis Babai doesn't construct the graph explicitly for $Q_8$. I'm just referring to the graph that Babai constructs in his proof for an arbitrary group $G$ in the special case of $Q_8$. $\endgroup$ – Jim Belk Jun 9 '15 at 6:39
  • $\begingroup$ Ah, I see, I had only glanced at the proof and didn't realize it was constructive, thanks for pointing this out. $\endgroup$ – Travis Jun 9 '15 at 7:25
  • $\begingroup$ A natural way to look for graphs with fewer edges is to take the graph in your answer, remove a set of corresponding (i.e., like-colored) edges, and see whether the automorphism group enlarges or not. Is there any reason, a priori, why any such graph produced this way would have a larger automorphism group? $\endgroup$ – Travis Jun 9 '15 at 7:29
0
$\begingroup$

What is the minimal number of vertices of a graph $\Gamma$ for which $\text{Aut}(\Gamma) \cong Q_8$? What is an example of such a graph that achieves this minimum? Among such graphs, which has (have) the minimal number of edges?

There has been progress on this question since I asked it three years ago: While Jim Belk's answer establishes that a graph $\Gamma = (V, E)$ with automorphism group $Q_8$ must have $|V| \geq 16$ (I don't know the earliest reference for this fact), Graves, Graves, & Lauderdale recently showed (2018) that the graphs with $|V| = 16$ and $\operatorname{Aut}(\Gamma) \cong Q_8$ satisfy the sharp bound $|E| \geq 44$.

Probably the article includes an example of a graph realizing the above minimum, but I cannot find an ungated copy and am away from my institution at the moment.

This REU presentation shows that if we allow more vertices we can find a graph with $\operatorname{Aut}(\Gamma) \cong Q_8$ and $|E| = 40$ and that this is a sharp lower bound for graphs with $|V| \leq 20$.

Graves, C.; Graves, S.J.; Lauderdale, L-K. "Smallest graphs with given generalized quaternion automorphism group." J Graph Theory. 87 (2018), 430-442. https://doi.org/10.1002/jgt.22166


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.