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