The diameter of random Cayley digraphs of given degree
classification
🧮 math.CO
keywords
cayleydiameterdigraphsprobabilityrandomaroundasymptoticallyasymptotics
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.