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 ${\sigma }_1,\dots ,{\sigma }_r\in S_N$ and evaluating $w\left({\sigma }_1,\dots ,{\sigma }_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+\theta \left(N^{1-\pi \left(w\right)}\right)$, where $\pi \left(w\right)$ is the smallest rank of a subgroup $H\le F$ containing $w$ as a non-primitive element. We show that $\pi \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^{-\pi \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

References in corpus (19)

• FI-modules and stability for representations of symmetric groups
• Representation theory and homological stability
• Second Order Freeness and Fluctuations of Random Matrices: II. Unitary Random Matrices
• Expansion of Random Graphs: New Proofs, New Results
• Measure Preserving Words are Primitive
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Combinatorial aspects of Connes's embedding conjecture and asymptotic distribution of traces of products of unitaries
• Primitive Words, Free Factors and Measure Preservation
• Stable commutator length is rational in free groups
• Words Maps and Spectra of Random Graph Lifts
• Matrix Group Integrals, Surfaces, and Mapping Class Groups I: $U(n)$
• Stallings Graphs, Algebraic Extensions and Primitive Elements in F2
• Growth of Primitive Elements in Free Groups
• Some Orbits of Free Words that are Determined by Measures on Finite Groups
• Expansion in simple groups
• On algebraic extensions and decomposition of homomorphisms in free groups
• A Note on the Trace Method for Random Regular Graphs
• Short, highly imprimitive words yield hyperbolic one-relator groups
• Automorphism-invariant positive definite functions on free groups

Cited by in corpus (6)

• The Asymptotic Statistics of Random Covering Surfaces
• Some Orbits of Free Words that are Determined by Measures on Finite Groups
• A Note on the Trace Method for Random Regular Graphs
• Matrix Group Integrals, Surfaces, and Mapping Class Groups II: $\mathrm{O}\left(n\right)$ and $\mathrm{Sp}\left(n\right)$
• Core Surfaces
• Word Measures on $G{L}_N(q)$ and Free Group Algebras