Random permutations acting on $k$--tuples have near--optimal spectral
gap for $k=\mathrm{poly}(n)$
Random permutations acting on $k$--tuples have near--optimal spectral
gap for $k=\mathrm{poly}(n)$
We extend Friedman's theorem to show that, for any fixed $r$, the random $2r$--regular Schreier graphs depicting the action of $r$ random permutations of $[n]$ on $k_{n}$--tuples of distinct elements in $[n]$ are a.a.s. weakly Ramanujan, for any $k_{n}\leq n^{\frac{1}{12}-\epsilon}.$ Previously this was known only for $k$--tuples where $k$ is …