12
$\begingroup$

Let $G=(V,E)$ be a simple, undirected graph. By $\newcommand{\Aut}{\text{Aut}}\Aut(G)$ we denote the collection of graph isomorphisms $\varphi:G\to G$. We let $$E(\Aut(G)) =\big\{\{\varphi, \psi\}:\varphi, \psi \in \Aut(G)\text{ and } \{\varphi(v),\psi(v)\}\in E\text{ for all }v\in V\big\}.$$ So $\big(\Aut(G), E(\Aut(G)\big)$ is a simple, undirected graph.

Question. If $\kappa$ is a cardinal, is there a connected graph $G=(V,E)$ with $|V|\geq \kappa$ and $G \cong \Aut(G)$?

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ It seems that the adjacency graph on the integers is a countably infinite instance, but I don't yet see how to make uncountable instances. $\endgroup$
    – Joel David Hamkins
    Commented May 21 at 12:43
  • 3
    $\begingroup$ There is also $x\mapsto -x$. Thus $Aut(\mathbb{Z})$ should have two components. $\endgroup$
    – HenrikRüping
    Commented May 21 at 12:55
  • 3
    $\begingroup$ Ah, darn. You are right. So do we have any examples? $\endgroup$
    – Joel David Hamkins
    Commented May 21 at 12:57
  • 3
    $\begingroup$ @JoelDavidHamkins The complete graph $K_2$ is a (trivial) connected example. $\endgroup$
    – Zerox
    Commented May 21 at 13:18
  • 6
    $\begingroup$ One simple observation: for any $\newcommand{\Aut}{\mathrm{Aut}}G$, $\Aut(G)$ is always vertex-transitive, since for any $f, g$, left-multiplication by $gf^{-1}$ is an automorphism sending $f$ to $g$. So if $G \simeq \Aut(G)$, then $G$ must be vertex-transitive, for starters. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented May 21 at 14:18

1 Answer 1

Reset to default
12
$\begingroup$

I will prove that if $G \cong \mathrm{Aut}(G)$ and $G$ is finite, then $G$ is the Cayley graph of a commutative group of exponent $2$. Then with Godsil's theorem about the existence of graphical regular representation (see page 32 of this, sadly I have no access to the original paper) there are examples with arbitrary large finite cardinals.

Let's denote $Q(G)$ the automorphism group of any graph $G$. Then $\mathrm{Aut}(G)$ is a graph with vertices indexed by $Q(G)$. Suppose $G \cong \mathrm{Aut}(G)$, one has $\mathrm{Aut}(G) \cong \mathrm{Aut}(\mathrm{Aut}(G))$. However, in $\mathrm{Aut}(\mathrm{Aut}(G))$, $2$ types of vertices can be found:

1. The left translations $\{l_g: \varphi \mapsto g\varphi \mid g \in Q(G)\}$. Given $g \in Q(G)$, $l_g$ is clearly a bijection on $V(\mathrm{Aut}(G))$. To see it also respects adjacency, observe that $$\{\varphi, \psi\} \in E(\mathrm{Aut}(G)) \implies \forall v \in V, \{\varphi(v), \psi(v)\}\in E \overset{g \in Q(G)}{\implies} \forall v \in V, \{g\varphi(v), g\psi(v)\}\in E \implies \{g\varphi, g\psi\}=l_g\{\varphi, \psi\} \in E(\mathrm{Aut}(G))$$ One can also get that $$\{\varphi, \psi\} \in E(\mathrm{Aut}(G)) \iff \forall v \in V, \{\varphi(v), \psi(v)\} \in E \iff \forall v \in V, g \in Q(G), \{\varphi g(v), \psi g(v)\} \in E \iff \forall g \in Q(G)=V(\mathrm{Aut}(G)), \{\varphi g, \psi g\}= \{l_\varphi(g), l_\psi(g)\} \in E \iff \{l_\varphi, l_\psi\} \in E(\mathrm{Aut}(\mathrm{Aut}(G)))$$ Therefore, the induced subgraph $L(G)$ of $\mathrm{Aut}(\mathrm{Aut}(G))$ with vertices $\{l_g\}$ is isomorphic to $\mathrm{Aut}(G)$.

2. The right translations $\{r_g^{-1}: \varphi \mapsto \varphi g \mid g \in Q(G)\}$. Given $g \in Q(G)$, $r_g^{-1}$ is clearly a bijection on $V(\mathrm{Aut}(G))$. To see it also respects adjacency, observe that $$\{\varphi, \psi\} \in E(\mathrm{Aut}(G)) \implies \forall v \in V, \{\varphi(v), \psi(v)\}\in E \overset{g \in Q(G)}{\implies} \forall v \in V, \{\varphi g(v), \psi g(v)\}\in E \implies \{\varphi g, \psi g\}=r_g^{-1}\{\varphi, \psi\} \in E(\mathrm{Aut}(G))$$ One can also get that $$\{\varphi, \psi\} \in E(\mathrm{Aut}(G)) \iff \forall v \in V, \{\varphi(v), \psi(v)\} \in E \iff \forall v \in V, g \in Q(G), \{g\varphi(v), g\psi(v)\} \in E \iff \forall g \in Q(G)=V(\mathrm{Aut}(G)), \{g\varphi, g\psi\}= \{r_\varphi^{-1}(g), r_\psi^{-1}(g)\} \in E \iff \{r_\varphi^{-1}, r_\psi^{-1}\} \in E(\mathrm{Aut}(\mathrm{Aut}(G)))$$ Therefore, the induced subgraph $R(G)$ of $\mathrm{Aut}(\mathrm{Aut}(G))$ with vertices $\{r_g^{-1}\}$ is also isomorphic to $\mathrm{Aut}(G)$.

When $G$ is a finite graph, the statement above immediately implies that $L(G) = R(G) = \mathrm{Aut}(\mathrm{Aut}(G)) \cong \mathrm{Aut}(G)$. Considering the image of $e \in Q(G) = V(\mathrm{Aut}(G))$ under the action of $Q(\mathrm{Aut}(G))$, one must have $l_g = r_g^{-1}$ in $Q(\mathrm{Aut}(G)) \cong Q(G)$, which means that $Q(G)$ is commutative.

Denote the set of vertices adjacent to $e$ by $S \subseteq Q(G)$, then since $\{l_g\}$ respects adjacency, the connected component of $e$ in $\mathrm{Aut}(G)$ is the Cayley graph of the group generated by $S$. Connectedness of $\mathrm{Aut}(G)$ implies that $\mathrm{Aut}(G)$ is the Cayley graph of the commutative group $Q(G)$ with generators $S$. $S$ is clearly symmetric: $\{e,g\} \in E(\mathrm{Aut}(G)) \implies l_{g^{-1}}\{e,g\} = \{g^{-1},e\} \in E(\mathrm{Aut}(G))$.

If $Q(G)$ is not of exponent $2$, then an element in $S$ must have order $k \ne 2$. Thus $g \mapsto g^{-1}$ is a non-trivial automorphism of $\mathrm{Aut}(G) = \mathrm{Cay}(Q(G),S)$ that is not of the form $\{l_g\}$, contradicting $L(G) = \mathrm{Aut}(G)$. The claim then follows.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ I don’t quite follow the step “Consider the image of the vertex indexed by $e \in Q(G)$ one must have $l_g = r^{-1}_g$.” At this point we have several different maps between graphs in play — you mean “the image” under which map, and “indexed by” under which map? And is $g$ meant to be that specific vertex, or a general element of $Q(G)$? $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented May 21 at 15:45
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine Sine $L(G) = R(G)$, they have the same vertices in $\mathrm{Aut}(\mathrm{Aut}(G))$. So we must have $\forall g \in Q(G), \exists h \in Q(G), l_g = r_h^{-1}$ in the group $Q(\mathrm{Aut}(G))$. Then $l_g(e) = r_h^{-1}(e)$ as vertex in $\mathrm{Aut}(G)$. $\endgroup$
    – Zerox
    Commented May 21 at 15:49
  • 2
    $\begingroup$ At least the claim “every element of $\newcommand{\Aut}{\mathrm{Aut}}\Aut(G)$ must have order 2” still holds, if I’m not mistaken. Once we know every automorphism is of the form $l_g$, any automorphism of $\Aut(G)$ that fixes $e$ must be the identity; in particular the “inversion” automorphism $f \mapsto f^{-1}$ must be the identity, i.e. every element of $\Aut(G)$ is of order 2. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented May 21 at 16:17
  • 2
    $\begingroup$ @PeterLeFanuLumsdaine Thanks. By the way, do you think the Cayley graph of $(\mathbb{Z}/2\mathbb{Z})^4$ with generators $\{a,b,c,d,a+b,a+c,a+b+c,a+b+d\}$ satisfies $G \cong \mathrm{Aut}(G)$? $\endgroup$
    – Zerox
    Commented May 21 at 17:31
  • 1
    $\begingroup$ I am still a bit confused. The Cayley-graph is usually an directed graph, and here we are looking at undirected graphs. Since all generators have order 2, we get for each edge in the directed version also an edge backwards. I assume these form together one undirected edge and this change does not affect the automorphism groups of the graphs. $\endgroup$
    – HenrikRüping
    Commented May 22 at 7:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .