Discrete Mathematics & Theoretical Computer Science, Vol 14, No 2 (2012)

Font Size:  Small  Medium  Large

Random Cayley digraphs of diameter 2 and given degree

Manuel E Lladser, Primoz Potocnik, Jozef Širáň, Mark C Wilson


We consider random Cayley digraphs of order $n$ with uniformly distributed generating sets of size $k$. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as $n\to\infty$ and $k=f(n)$, focusing on the functions $f(n)= \lfloor n^{\delta} \rfloor$ and $f(n)=\lfloor cn\rfloor$. In both instances we show that this probability converges to $1$ as $n\to\infty$ for arbitrary fixed $\delta\in (\frac{1}{2},1)$ and $c\in (0,\frac{1}{2})$, respectively, with a much larger convergence rate in the second case and with sharper results for Abelian groups.

Full Text: PDF PostScript