Given a finite group G and a set A of generators, the diameter diam(Γ(G,A)) of the Cayley graph Γ(G,A) is the smallest 𝓁 such that every element of G can be expressed as a word of length at most 𝓁 in A ⋃ A-1. We are concerned with bounding diam(G):= maxA diam(Γ(G,A)). It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n. In 2011, Helfgott and Seress gave a quasipolynomial bound exp((log n)4+ε). We will discuss a recent, much simplified version of the proof.
This video was produced by the Simons Institute, and forms part of the workshop Expanders and Extractors.
