Babai–Godsil–Imrich–Lovász conjecture on generic GRRs
Let ) be a group of order which is neither abelian nor generalised dicyclic. An inverse-closed subset of satisfies . A graphical regular representation (GRR) is a Cayley graph whose automorphism group is precisely the right-regular representation of .
Babai–Godsil–Imrich–Lovász conjecture. The proportion of inverse-closed subsets of such that is a GRR goes to as .
The conjecture asserts that, apart from abelian and generalised dicyclic groups, almost every inverse-closed Cayley graph is a GRR.
References
2 papers in this index state this conjecture (2013). The statement above is taken from the most recent of them; the others are arXiv:1306.3747.
Source: https://arxiv.org/abs/1310.0618 Babai, Godsil, Imrich and Lovász, Conjecture 2.1 (as attributed in the source)
Status
- Solved: Binzhou Xia and Shasha Zheng. Asymptotic enumeration of graphical regular representations (arXiv, 2022) https://arxiv.org/abs/2212.01875
Source: Joy Morris, Pablo Spiga and Gabriel Verret, “Automorphisms of Cayley graphs on generalised dicyclic groups”, arXiv:1310.0618 (2013).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.