Random permutations acting on $k$--tuples have near--optimal spectral gap for $k=\mathrm{poly}(n)$

Abstract

We extend Friedman's theorem to show that, for any fixed $r>1$, a random $2r$--regular Schreier graph associated with the action of $r$ uniformly random permutations of $[n]$ on $k_n$--tuples of distinct elements in $[n]$ has a near--optimal spectral gap with high probability, provided $k_n\le n^{\frac{1}{20}-\epsilon }.$ Previously this was known only for $k$--tuples where $k$ is fixed. In fact, we prove the stronger result of strong convergence of random permutations in irreducible representations of quasi--exponential dimension. Along the way, we give a new bound for the expected stable irreducible character of a random permutation obtained via a word map, showing that $\mathbb{E}\left[{\chi }^{\mu }\left(w({\sigma }_1,\dots ,{\sigma }_r)\right)\right]=O\left(\frac{1}{\dim {\chi }^{\mu }}\right)=O\left(n^{-k}\right)$, where $k$ is the number of boxes outside the first row of the Young diagram $\mu ,$ solving one aspect of a conjecture of Hanany and Puder. We obtain this bound using an extension of Wise's $w$--cycle conjecture.

corrected exponent in main theorem