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$.

44 pages. Several typos corrected. Referee comments incorporated

References in corpus (1)

• The trivial lower bound for the girth of $S_n$

Cited by in corpus (2)

• Word Measures on $G{L}_N(q)$ and Free Group Algebras
• Expansion in Cayley graphs, Cayley sum graphs and their twists