← All problems

Babai–Godsil–Imrich–Lovász conjecture on generic GRRs

13 years old · traced to

Let RR) be a group of order nn which is neither abelian nor generalised dicyclic. An inverse-closed subset SS of RR satisfies s∈S⇒s−1∈Ss\in S\Rightarrow s^{-1}\in S. A graphical regular representation (GRR) is a Cayley graph whose automorphism group is precisely the right-regular representation of RR.

Babai–Godsil–Imrich–Lovász conjecture. The proportion of inverse-closed subsets SS of RR such that Cay⁡(R,S)\operatorname{Cay}(R,S) is a GRR goes to 11 as n→∞n\to\infty.

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

Source: Joy Morris, Pablo Spiga and Gabriel Verret, “Automorphisms of Cayley graphs on generalised dicyclic groups”, arXiv:1310.0618 (2013).

Progress summary

Never refreshed

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.