5
$\begingroup$

If $\Gamma = C(G, S)$ is the (undirected) Cayley graph of a finite group $G$ with generating set $S$, then $G \le \operatorname{Aut}(\Gamma)$, the "full" automorphism group of $\Gamma$.

When is it true that $G \cong \operatorname{Aut}(\Gamma)$? In other words, when is a group $G$ (isomorphic to) the automorphism group of its own Cayley graph (via a specified generating set)?

Here, by "full" automorphism group, I mean the group of permutations of the vertex set that preserve adjacency (with no regard to the coloring that is usually associated with Cayley graphs).

$\endgroup$
  • $\begingroup$ To clarify: Is it possible to specify the required conditions based only on the structure of the group $G$ and generating set $S$, without explicitly looking at the graph structure? $\endgroup$ – M. Vinay Feb 6 '15 at 5:27
  • 1
    $\begingroup$ A simple remark is that $Aut(\Gamma)$ is the pointwise product of $\Gamma$ and $Aut(\Gamma)_1$, the stabilizer of 1, and the latter is a profinite group. Hence the question boils down to whether this profinite group $Aut(\Gamma)_1$ is trivial. Maybe the most fundamental question is whether this $Aut(\Gamma)_1$ is finite (since otherwise it's uncountable); equivalently it asks whether there exists a finite subset in $\Gamma$ whose fixator is trivial. $\endgroup$ – YCor Feb 6 '15 at 8:46
  • 1
    $\begingroup$ Information about $Aut(\Gamma)$ is available when the QI-study of $\Gamma$ is well-understood. More precisely, when you know all locally compact compactly generated groups quasi-isometric to $\Gamma$ (not only finitely generated ones! this is too narrow). Indeed, $Aut(\Gamma)$ is a totally disconnected group QI to $\Gamma$. In some cases (e.g., most lattices in semisimple Lie groups), $\Gamma$ is not QI to any such group except compact-by-discrete groups and this can help proving that $Aut(\Gamma)_1$ is finite. $\endgroup$ – YCor Feb 6 '15 at 8:53
7
$\begingroup$

First, some terminology: if $G\cong\mathrm{Aut}(\Gamma)$ then $\Gamma$ is often called a GRR (for graphical regular representation). This may help in looking for references. Determining whether a Cayley graph is a GRR given $G$ and $S$ is very difficult in general.

One necessary criterion is the following: let $\mathrm{Aut}(G,S)$ be the group of automorphisms of $G$ that preserve $S$. If $\Gamma$ is a GRR then $\mathrm{Aut}(G,S)=1$.

Sometimes, this is also sufficient, see for example:

-Godsil, C. D.; On the full automorphism group of a graph. Combinatorica 1 (1981), 243–256.

-Li, Cai Heng; Sim, Hyo-Seob; The graphical regular representations of finite metacyclic p-groups. European J. Combin. 21 (2000), 917–925.

In fact, the semidirect product of $G$ and $\mathrm{Aut}(G,S)$ is exactly the normaliser of $G$ in $\mathrm{Aut}(\Gamma)$, so that part is somewhat under control, but the part of $\mathrm{Aut}(\Gamma)$ that does not normalise $G$ is very difficult to deal with in general.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

A group $G$ is said to admit a graphical regular representation (GRR) if there is a graph $\Gamma$ such that $Aut(\Gamma) \cong G$ and $G$ acts regularly on the vertices of $\Gamma$. Such a graph is called a GRR of the group $G$.

A graph $\Gamma$ is said to be a GRR if $Aut(\Gamma)$ acts regularly on the vertices of $X$. Sabidussi showed that a connected graph $\Gamma$ is isomorphic to a Cayley graph iff $Aut(\Gamma)$ contains a regular group. A Cayley graph $C(G,S)$ is said to be a GRR if its automorphism group is $G$ (which is the smallest possible full automorphism group for a Cayley graph $C(G,S)$). The question of determining, for a given $G,S$, whether $C(G,S)$ is a GRR, is a difficult and generally open problem.

The problem of which groups admit GRRs was resolved in the 1970s by the work of several authors and finally by (Godsil, 1978). It was proved that the only two infinite families of finite groups which do not admit GRRs are the abelian groups of exponent at least 3 and the generalized dicyclic groups. Each Cayley graph $C(G,S)$ on these two groups has a nontrivial automorphism so that $Aut(C(G,S))$ is strictly larger than $G$. Hence, these two families of groups do not admit GRRs. For all other groups, it is possible to construct at least one GRR for the group.

Recall that if $G$ is any group besides the two exceptions mentioned above, there is an $S$ such that $C(G,S)$ is a GRR. It was conjectured in (Babai and Godsil, "On the automorphism group of almost all Cayley graphs", Eur. J. Comb., 1982, Conjecture 2.1) that almost all Cayley graphs of such non-exceptional groups are GRRs.

Both the right regular representation $R(G)$ and the set $Aut(G,S)$ of automorphisms of $G$ that fixes $S$ setwise are automorphisms of the Cayley graph $C(G,S)$. $Aut(G,S)$ also fixes the identity vertex $e$. Observe that $Aut(C(G,S))$ equals $R(G) Aut(C(G,S))_e$, which contains $R(G)Aut(G,S)$. Thus, an equivalent condition for the Cayley graph $C(G,S)$ to be a GRR is that $Aut(C(G,S))_e =1$, and a necessary condition for $C(G,S)$ to be a GRR is that $Aut(G,S)=1$.

Since $Aut(G,S)$ might be easier to determine than $Aut(C(G,S))_e$, an open problem posed by (Godsil, "The automorphism groups of some cubic Cayley graphs", European Journal of Combinatorics, Eur. J. Comb., 25–32, 1983) is to determine conditions under which $C(G,S)$ is a GRR iff $Aut(G,S)=1$. Partial solutions to this problem include (Godsil, 1981, Combinatorica), (Li and Sim, Eur. J. Comb, 2000) and (Godsil, Eur. J. Comb, 1983).

If $G$ is abelian of exponent larger than 2 or generalized dicyclic, then $C(G,S)$ admits $G$ and a particular nontrivial map $i$ as automorphisms, and hence, $C(G,S)$ admits $G \rtimes \langle i \rangle$ (a group strictly larger than $G$) as a subgroup of automorphisms. Hence, $G$ does not admit a GRR. An open question was to determine whether almost all Cayley graphs of $G$ have the smallest possible automorphism group $G \rtimes \langle i \rangle$. This question was answered in the affirmatively recently by (Dobson, Spiga, and Verret, arXiv, 2014) for abelian groups and by (Morris, Spiga and Verret, 2015) for generalized dicyclic groups.

A Cayley graph $C(G,S)$ is said to be normal if $Aut(C(G,S))$ is exactly equal to $R(G) Aut(G,S)$. An open problem in the literature is to determine which Cayley graphs $C(G,S)$ are normal; see (Xu, "Automorphism groups and isomorphisms of Cayley digraphs", Discrete Math., 309–319, 1998). A conjecture is that almost all Cayley graphs are normal. More specifically, the conjecture is that if $G \ne Q_8 \times C_2^m$ is a group of order $n$, then the probability that a random Cayley graph of $G$ is normal approaches 1 as $n \rightarrow \infty$. A Cayley graph which is a GRR is also a normal Cayley graph, and so the conjecture that almost all Cayley graphs are normal is weaker than the conjecture that almost all Cayley graphs are GRRs. Non-normal Cayley graphs are rare, and to determine, for a given $G,S$, whether $C(G,S)$ is normal, is an open problem.

| cite | improve this answer | |
$\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.