Babai–Godsil–Imrich–Lovász conjecture on almost all Cayley graphs being GRRs
Babai–Godsil–Imrich–Lovász conjecture on almost all Cayley graphs being GRRs
Let be a group of order that is neither abelian of exponent greater than nor generalized dicyclic. For a subset , write for the Cayley digraph with vertex set and arcs whenever . If , this is a Cayley graph. A graphical regular representation (GRR) is a Cayley graph whose full automorphism group is acting regularly on its vertices.
Babai–Godsil–Imrich–Lovász conjecture. The proportion of inverse-closed subsets of such that is a GRR of approaches as approaches infinity.
The paper states that this conjecture is completely solved in the affirmative, with an explicit lower bound for the proportion and hence convergence to .
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
Binzhou Xia and Shasha Zheng, “Asymptotic enumeration of graphical regular representations”, arXiv:2212.01875 (2023).
Additional references
3 papers in this index state this conjecture (2013–2022). The statement above is taken from the most recent of them; the others are arXiv:1310.0618, arXiv:1306.3747.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.