Talks
Spring 2017

The Diameter of the Symmetric Group: Ideas and Tools

Friday, February 3rd, 2017 2:00 pm2:45 pm

Add to Calendar

Given a finite group $G$ and a set $A$ of generators, the diameter $\diam(\Gamma(G,A))$ of the Cayley graph $\Gamma(G,A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding $\diam(G):= \max_A\diam(\Gamma(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+epsilon))). We will discuss a recent, much simplified version of the proof.