skip to content

Department of Pure Mathematics and Mathematical Statistics

A fundamental open problem on the geometry of Cayley graphs is Babai's Diameter Conjecture, which states that the diameter of any connected Cayley graph on a nonabelian finite simple group $G$ is at most polylogarithmic in $|G|$. A natural extremal variant, also open in general, asks for the maximum possible diameter given the density of the generating set. In this talk, we consider the alternating permutation groups $A_n$, for which Helfgott and Seress showed that the diameter of any Cayley graph is at most quasipolynomial in $n$. We will present an essentially optimal upper bound on the diameter when the density of the generating set is at least $2^{-O(n)}$. Our proof combines combinatorial, analytic and algebraic arguments, with the key ingredient being a new sharp hypercontractive inequality in $S_n$. This is joint work with Noam Lifshitz.

Further information

Time:

26Feb
Feb 26th 2026
14:30 to 15:30

Venue:

MR12

Speaker:

Peter Keevash (Oxford)

Series:

Combinatorics Seminar