Babai’s conjecture asserts that the diameter of the Cayley graph of any finite simple group G is bounded by (log |G|)O(1). This conjecture has been resolved for groups of bounded rank, but for groups of unbounded rank such as SLn(2) it is wide open. Even for random generators, only the case of alternating groups is resolved. In this talk we sketch the proof of Babai’s conjecture for SLn(p), p = O(1), with at least three random generators. The proof extends to other classical groups over 𝔽q if we have at least q100 random generators. The heart of the proof consists of showing that the Schreier graph of SLn(q) acting on 𝔽qn with respect to q100 random generators is an expander graph.
This video was produced by Tel Aviv University as part of its algebra seminar.
