Asymptotic enumeration conjecture for graphical regular representations

About 14 years old · traced to

Let d-valentd\text{-valent} vertex-transitive graphs, Cayley graphs, and graphical regular representations (GRRs) be counted up to order at most nn by VTd(n)VT_d(n), CAYd(n)CAY_d(n), and GRRd(n)GRR_d(n), respectively. GRR enumeration conjecture. There exist positive constants aa, bb and cc such that, for every d≥3d\geq 3,

nadlog⁡n−c≤GRRd(n)≤CAYd(n)≤VTd(n)≤nbdlog⁡n.n^{ad\log n}-c\leq GRR_d(n)\leq CAY_d(n)\leq VT_d(n)\leq n^{bd\log n}.

This extends the established bounds for valency 33 to every fixed valency d≥3d\geq 3; the conjecture remains 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.