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)

Download author version

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.

Leave a Reply

Your email address will not be published. Required fields are marked *