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.
