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

Ewan Cassidy

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…