The diameter of random Cayley digraphs of given degree

Abstract

We consider random Cayley digraphs of order $n$ with uniformly distributed generating set of size $k$. Specifically, we are interested in the asymptotics of the probability such a Cayley digraph has diameter two as $n\to \infty$ and $k=f(n)$. We find a sharp phase transition from 0 to 1 at around $k=\sqrt{n\log n}$. In particular, if $f(n)$ is asymptotically linear in $n$, the probability converges exponentially fast to 1.

11 pages