Babai's conjecture for high-rank classical groups with random generators

Abstract

Let $G={\mathrm{SCl}}_n(q)$ be a quasisimple classical group with $n$ large, and let $x_1,\dots ,x_k\in G$ random, where $k\ge q^C$. We show that the diameter of the resulting Cayley graph is bounded by $q^2{n}^{O(1)}$ with probability $1-o(1)$. In the particular case $G={\mathrm{SL}}_n(p)$ with $p$ a prime of bounded size, we show that the same holds for $k=3$.

arXiv comment44 pages. Several typos corrected. Referee comments incorporated

References in corpus (7)

• Generalizations of the Kolmogorov-Barzdin embedding estimates
• Character Levels and Character Bounds
• The trivial lower bound for the girth of $S_n$
• Diameter Bound for Finite Simple Groups of Large Rank
• The Probability of Generating the Symmetric Group
• An improved diameter bound for finite simple groups of Lie type
• Random Generation of the Special Linear Group

Cited by in corpus (3)

• Word Measures on $G{L}_N(q)$ and Free Group Algebras
• Expansion in Cayley graphs, Cayley sum graphs and their twists
• Fundamental groups and group presentations with bounded relator lengths