Fixed-valency GRR density: is the proportion of $k$-valent Cayley graphs that are graphical regular representations tending to 1?

For each fixed integer valency $k\ge 3$, it is open whether the proportion of isomorphism classes of connected $k$-valent Cayley graphs with at most $n$ vertices whose full automorphism group is as small as possible (graphical regular representations, GRRs) tends to $1$ as $n\to\infty$, and dually whether the proportion that are arc-transitive tends to $0$. The question is the bounded-degree (sparse-regime) counterpart of the Babai–Godsil–Imrich–Lovász conjecture, which Xia and Zheng settled in 2023 in the dense regime: for each fixed finite group outside two exceptional families, the proportion of inverse-closed subsets yielding GRRs tends to $1$. A complete census of cubic Cayley graphs up to order $5000$ and quartic ones up to order $1025$ by Evans and Potočnik (2025) found numerically increasing GRR proportions and decreasing arc-transitive proportions, and posed the fixed-valency asymptotics as Problems 1 and 2 of that paper. No known technique addresses it: the existing proofs average over connection sets of unrestricted size, an argument structure that collapses when the valency is fixed.

Background

A Cayley graph is constructed from a finite group $G$ and a subset $S\subseteq G$ (a Cayley set) by taking the elements of $G$ as vertices and joining $x$ to $y$ whenever $xy^{-1}\in S$; requiring $S$ to be inverse-closed gives an undirected graph, excluding the identity prevents loops, and requiring $S$ to generate $G$ makes the graph connected (the convention used in the census paper from which this problem comes). Since the right-regular action of $G$ on itself preserves adjacency, $G$ always embeds in the automorphism group $\mathrm{Aut}(\mathrm{Cay}(G,S))$; the graph is a graphical regular representation (GRR) of $G$ when equality holds, i.e. when the automorphism group is as small as possible. At the opposite extreme, a graph is arc-transitive when its automorphism group acts transitively on ordered adjacent pairs; an arc-transitive Cayley graph of valency at least $2$ is never a GRR, because transitivity on arcs forces the stabilizer of a vertex to be nontrivial while in a GRR it is trivial. Which finite groups admit at least one GRR was completely classified by the early 1980s: apart from abelian groups of exponent greater than $2$, the generalized dicyclic groups (non-abelian groups with an abelian subgroup $A$ of index $2$ and an element $x$ of order $4$ inverting $A$), and thirteen small solvable groups (of order at most $32$), every finite group has one. The harder question is frequency. Babai and Godsil conjectured in 1982, together with Imrich and Lovász, that for each fixed finite group outside the two exceptional families the proportion of inverse-closed subsets $S$ for which $\mathrm{Cay}(G,S)$ is a GRR tends to $1$ as the group order grows. Morris and Spiga proved the corresponding statement for directed Cayley graphs in 2021, and Xia and Zheng proved the undirected version in 2023 with effective error terms, confirming also Xu's conjecture that almost all Cayley graphs are normal (i.e. the regular group is normal in the automorphism group); related per-group asymptotic enumeration of Cayley digraphs and Cayley graphs was developed by Morris–Spiga and Morris–Moscatiello–Spiga. All of these results fix a group and average over connection sets of unrestricted size — a dense regime where 'almost all subsets' arguments apply. The problem below asks the same question in the sparse regime where the valency $k$ (the size of the Cayley set) is held fixed, and where the population consists of all Cayley graphs of order at most $n$ across all groups, counted up to graph isomorphism. It was prompted by the census of Evans and Potočnik, who generated complete irredundant lists of connected cubic Cayley graphs with at most $5000$ vertices ($1{,}939{,}864$ graphs) and quartic ones with at most $1025$ vertices ($11{,}361{,}600$ graphs) using GAP (Groups, Algorithms, Programming — a computational algebra system) for group generation and nauty (a graph isomorphism and automorphism computation package) for isomorph reduction, and observed that the cumulative proportion of GRRs grows with the order (more slowly for quartic graphs, with a marked gap between odd and even orders) while the proportion of arc-transitive graphs decays towards $0$.

Problem Statement

For an integer $k\ge 3$, let $\mathcal{C}_k(n)$ denote the set of isomorphism classes of connected $k$-valent Cayley graphs on at most $n$ vertices (equivalently, graphs $\mathrm{Cay}(G,S)$ where $|G|\le n$ and $S$ is an inverse-closed, identity-excluding generating set of $G$ of size $k$). Let $g_k(n)$ be the proportion of members of $\mathcal{C}_k(n)$ that are graphical regular representations — graphs whose full automorphism group is exactly the right-regular action of the underlying group — and let $t_k(n)$ be the proportion that are arc-transitive, i.e. whose automorphism group acts transitively on ordered adjacent pairs of vertices. The problem, posed as Problems 1 and 2 of Evans and Potočnik's census with the two questions sharing one objective — showing that the typical $k$-valent Cayley graph of bounded order is symmetry-minimal — is: for every fixed integer $k\ge 3$, determine whether

$$\lim_{n\to\infty} g_k(n) = 1 \quad\text{and}\quad \lim_{n\to\infty} t_k(n) = 0.$$

A positive answer to the first limit implies the second, since an arc-transitive Cayley graph of valency at least $2$ is never a GRR: establishing $\lim_{n\to\infty} g_k(n)=1$ for every $k\ge 3$ is therefore a complete resolution, settling both limits, whereas if the first limit is refuted for some $k$ the second must still be established or refuted for that $k$. Graphs are counted up to isomorphism across all finite groups of order at most $n$.

References

1. Rhys J. Evans and Primož Potočnik, "A census of Cayley graphs", arXiv preprint arXiv:2512.05406 (2025), https://arxiv.org/abs/2512.05406
2. Binzhou Xia and Shasha Zheng, "Asymptotic enumeration of graphical regular representations", Proceedings of the London Mathematical Society (3) 127 (2023), no. 5, 1424–1450, doi:10.1112/plms.12563, https://doi.org/10.1112/plms.12563 (preprint arXiv:2212.01875)
3. László Babai and Chris D. Godsil, "On the automorphism groups of almost all Cayley graphs", European Journal of Combinatorics 3 (1982), no. 1, 9–15, doi:10.1016/S0195-6698(82)80003-6, https://doi.org/10.1016/S0195-6698(82)80003-6
4. J. Morris and P. Spiga, "Asymptotic enumeration of Cayley digraphs", Israel Journal of Mathematics 242 (2021), 401–459, doi:10.1007/s11856-021-2150-0, https://doi.org/10.1007/s11856-021-2150-0
5. J. Morris, M. Moscatiello and P. Spiga, "On the asymptotic enumeration of Cayley graphs", Annali di Matematica Pura ed Applicata (4) 201 (2022), 1417–1461, doi:10.1007/s10231-021-01163-w, https://doi.org/10.1007/s10231-021-01163-w