# The diameter of random Cayley digraphs of given degree

Manuel Lladser, Primoz Potocnik, Jana Siagova, Jozef Siran and Mark C. Wilson, submitted to Random Structures and Algorithms, June 2006 (12 pages)

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 $ntoinfty$ and $k=f(n)$. We find a sharp phase transition from 0 to 1 as the order of growth of $f(n)$ increases past $sqrt{n log n}$. In particular, if $f(n)$ is asymptotically linear in $n$, the probability converges exponentially fast to 1.