Word Measures on Symmetric Groups

Abstract

Fix a word $w$ in a free group $F$ on $r$ generators. A $w$-random permutation in the symmetric group $S_N$ is obtained by sampling $r$ independent uniformly random permutations $\ddot{I}{ƒ}_1,\dots ,\ddot{I}{ƒ}_r\in S_N$ and evaluating $w\left(\ddot{I}{ƒ}_1,\dots ,\ddot{I}{ƒ}_r\right)$. In [arXiv:1104.3991, arXiv:1202.3269] it was shown that the average number of fixed points in a $w$-random permutation is $1+\hat{I}¸\left(N^{1-\ddot{I}€\left(w\right)}\right)$, where $\ddot{I}€\left(w\right)$ is the smallest rank of a subgroup $H\le F$ containing $w$ as a non-primitive element. We show that $\ddot{I}€\left(w\right)$ plays a role in estimates of all stable characters of symmetric groups. In particular, we show that for all $t\ge 2$, the average number of $t$-cycles is $\frac{1}{t}+O\left(N^{-\ddot{I}€\left(w\right)}\right)$. As an application, we prove that for every $s$, every $\epsilon >0$ and every large enough $r$, Schreier graphs with $r$ random generators depicting the action of $S_N$ on $s$-tuples, have second eigenvalue at most $2\sqrt{2r-1}+\epsilon$ asymptotically almost surely. An important ingredient in this work is a systematic study of not-necessarily connected Stallings core graphs.

53 pages, 3 figures. This version: fixed a minor gap in Appendix A