GRR density conjecture for fixed-valency Cayley graphs

About 14 years old · traced to

For fixed d≥3d\geq 3, let CAYd(n)CAY_d(n) be the number of isomorphism classes of dd-valent Cayley graphs of order at most nn, and let GRRd(n)GRR_d(n) count those that are graphical regular representations. GRR density conjecture. For every d≥3d\geq 3,

GRRd(n)CAYd(n)→1(n→∞).\frac{GRR_d(n)}{CAY_d(n)}\to 1 \qquad (n\to\infty).

This asserts that almost all fixed-valency Cayley graphs are GRRs under the paper's enumeration convention. The source contrasts this with a generating-set proportion formulation and leaves the graph-counting version open.

References

Primary source

Primoz Potocnik, Pablo Spiga and Gabriel Verret, “Asymptotic enumeration of vertex-transitive graphs of fixed valency”, arXiv:1210.5736 (2012).

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.