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

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 }\mathrm{.}$ 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 }(w({\sigma }_1,\dots ,{\sigma }_r))\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.