Sean Eberhard

Diameter of high-rank classical groups with random generators

A conjecture due to Babai predicts a six-degrees-of-separation-type behaviour for finite simple groups. The conjecture is that the diameter of a Cayley graph of G is always bounded by (log |G|)^O(1). I will talk mainly about high-rank groups such as S_n and SL_n(2) with random generators. We can prove the conjecture for SL_n(q), q bounded, provided we have at least q^100 random generators. The heart of the proof consists of showing that the Schreier graph of SL_n(q) acting on F_q^n with respect to q^100 random generators is an expander graph. The proof of this uses the so-called trace method, which goes back to Wigner and his semicircle law for random matrices. I may make some noises about how the proof generalizes to other classical groups. All joint work with Urban Jezernik.