Conjecture on the limiting distribution of random Cayley graph diameters

About 20 years old · traced to

Let qq be prime, let g1,…,gkg_1,\ldots,g_k be independent uniformly random generators of the cyclic group Zq{\mathbb Z}_q, and let Diam(q,k)Diam(q,k) denote the diameter of the resulting directed Cayley graph. The same notation may be used for the corresponding undirected Cayley graph with generating set {g1,−g1,…,gk,−gk}\{g_1,-g_1,\ldots,g_k,-g_k\}. Diameter distribution conjecture. The normalized diameter

Diam(q,k)qk\frac{Diam(q,k)}{\sqrt[k]{q}}

converges in distribution to some distribution D(k)D(k) on R{\mathbb R} whose support is non-compact. The preceding upper and lower bounds show that the normalization by qk\sqrt[k]{q} is of the correct order and that the limiting behavior is non-degenerate in the stated sense; the existence and non-compactness of the limiting distribution remain open in the source.

References

Primary source

Gideon Amir and Ori Gurel-Gurevich, “The diameter of a random Cayley graph of Z_q”, arXiv:math/0609620 (2009).

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.