The diameter of random Cayley digraphs of given degree

Simple item page
dc.creatorPotočnik, Primož
dc.creatorŠiráň, Jozef
dc.creatorŠiagiová, Jana
dc.creatorLladser, Manuel E.
dc.creatorWilson, Mark C.
dc.date2007-06-24
dc.date.accessioned2026-07-07T08:12:10Z
dc.date.available2026-07-07T08:12:10Z
dc.descriptionWe 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.
dc.description11 pages
dc.identifierhttps://arxiv.org/abs/0706.3539
dc.identifierhttp://arxiv.org/abs/0706.3539
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/132359
dc.subjectCombinatorics
dc.subject05C80; 05C20
dc.titleThe diameter of random Cayley digraphs of given degree
dc.typetext

Files

Collections

arXiv