Asymptotic enumeration of Cayley digraphs

• DOI: 10.1007/s11856-021-2150-0
• Publication Date: 2021-05-25T04:27:42Z
• Authors: Joy Morris; Pablo Spiga
• Keywords: Cayley graph; Enumeration; Cayley's theorem; Infinity

In this paper we show that almost all Cayley digraphs have automorphism group as small as possible; that is, they are digraphical regular representations (DRRs). More precisely, we show that as $r$ tends to infinity, for every finite group $R$ of order $r$, out of all possible Cayley digraphs on $R$ the proportion whose automorphism group is as small as possible tends to $1$. This proves a natural conjecture first proposed in $1982$ by Babai and Godsil.<br/>24 pages<br/>