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.
Articolo in rivista - Articolo scientifico
Babai-Godsil conjecture
English
2021
242
1
401
459
open
Morris, J., Spiga, P. (2021). Asymptotic enumeration of Cayley digraphs. ISRAEL JOURNAL OF MATHEMATICS, 242(1), 401-459 [10.1007/s11856-021-2150-0].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/415915
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
Social impact