pith. sign in

arxiv: 0706.3539 · v1 · submitted 2007-06-24 · 🧮 math.CO

The diameter of random Cayley digraphs of given degree

classification 🧮 math.CO
keywords cayleydiameterdigraphsprobabilityrandomaroundasymptoticallyasymptotics
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.