Further Results and Discussions on Random Cayley Graphs

MaRDI QIDQ6328738zbMATH OpenFDO

Authors Jonathan Hermon, Sam Olesker-Taylor

Publication date 7 November 2019

Mathematics Subject Classification ID

Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Finite nilpotent groups, (p)-groups (20D15) Continuous-time Markov processes on discrete state spaces (60J27) Processes in random environments (60K37)

Abstract: Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1llklesssimlog|G|$. The results of this article supplement those in the three main papers on random Cayley graphs. The majority of the results are inspired by a `universality' conjecture of Aldous and Diaconis (1985). To start, we study the limit profile of cutoff for the simple random walk on this random graph, as well as a detailed investigation into mixing properties when $G=mathbb{Z}_p^d$ with $p$ prime. We then exposit a proof of Diaconis and Saloff-Coste (1994) establishing lack of cutoff when $kasymp1$. We move onto discussing material from our companion paper on matrix groups. We then study distance of a typical element of $G$ from the identity in an $L_q$-type graph distance in the Abelian set-up. Finally, we give necessary and sufficient conditions for $k$ independent uniform elements of $G$ to generate $G$, ie for the random Cayley graph to be connected, based on work of Pomerance (2001). The aforementioned results all hold with high probability over the random Cayley graph.

This page was built for publication: Further Results and Discussions on Random Cayley Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328738)