Babai–Godsil conjecture on almost all Cayley graphs being GRRs
Babai–Godsil conjecture on almost all Cayley graphs being GRRs
Let be a finite group, and let be an inverse-closed subset of . The Cayley graph has vertex set and edges determined by ; a graphical regular representation (GRR) is a Cayley graph whose full automorphism group is acting regularly on its vertices. A group is generalised dicyclic if it belongs to the corresponding excluded family, and an abelian group has exponent greater than when some element has order greater than .
Babai–Godsil conjecture. If is not generalised dicyclic or abelian of exponent greater than , then for almost all inverse-closed subsets of , is a GRR.
This conjecture concerns the asymptotic prevalence of graphical regular representations among Cayley graphs. Godsil's theorem characterizes the groups admitting at least one GRR, but the supplied source does not state whether this stronger almost-all assertion has been resolved.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Joy Morris, Mariapia Moscatiello and Pablo Spiga, “On the asymptotic enumeration of Cayley graphs”, arXiv:2005.07687 (2020).
Additional references
3 papers in this index state this conjecture (2013–2020). The statement above is taken from the most recent of them; the others are arXiv:1911.09444, arXiv:1306.3747.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.