Random generators of the symmetric group: diameter, mixing time and spectral gap

Harald Helfgott
Centre National de la Recherche Scientifique (CNRS)

Let g, h be a random pair of generators of G=Sym(n) or G=Alt(n). We show that, with probability tending to 1 as n tends to infinity, (a) the diameter of G with respect to S={g,h,g^{-1},h^{-1}} is at most O(n^2 (log n)^c), and (b) the mixing time of G with respect to S is at most O(n^3 (log n)^c). (Both c and the implied constants are absolute.)

These bounds are far lower than the strongest worst-case bounds known (in Helfgott-Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap.

(Joint with A. Seress (deceased) and A. Zuk)


Back to Workshop IV: Finding Algebraic Structures in Extremal Combinatorial Configurations