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.
Morris, J., Spiga, P. (2021). Asymptotic enumeration of Cayley digraphs. ISRAEL JOURNAL OF MATHEMATICS, 242(1), 401-459 [10.1007/s11856-021-2150-0].
Asymptotic enumeration of Cayley digraphs
Spiga P.
2021
Abstract
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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Spiga-2021-Israel J Math-preprint.pdf
accesso aperto
Descrizione: Article
Tipologia di allegato:
Submitted Version (Pre-print)
Licenza:
Creative Commons
Dimensione
440.17 kB
Formato
Adobe PDF
|
440.17 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
