论文标题
对称群体的单词度量
Word Measures on Symmetric Groups
论文作者
论文摘要
修复$ r $发电机上的免费组$ f $中的单词$ w $。对称组中的A $ W $ -random排列$ s_n $是通过抽样$ r $ r $独立的统一随机排列$σ_{1}，\ ldots，σ_{r} \ in s_ {n} $ in s_ {n} $和评估$ w \ w \ w \ feust（n} $ w \ feft（1} $} $} $}，在[arxiv：1104.3991，arxiv：1202.3269]中，显示出$ w $ -random置换中的固定点的平均数量为$ 1+θ\ left（n^{1-π\ left（w \ w \ orir）} \ right）一个非关键元素。我们表明$π\ left（w \ right）$在对称组的所有稳定字符的估计中都起着作用。特别是，我们表明，对于所有$ t \ ge2 $，$ t $ -cycles的平均数为$ \ frac {1} {t} {t}+o \ left（n^{ - π\ left（w \ right）} \ right）$。作为一个应用程序，我们证明，对于每$ s $，每$ \ varepsilon> 0 $以及每一个足够大的$ r $，schreier图形，带有$ r $ r $随机生成器，描绘$ s $ s $ -tuples上的$ s_ {n} $的动作，最多有第二个eigenvalue $ s eigenvalue，最多可以在$ 2 \ sqrt {2r-sqrt {2r-asct+vareps+vareps+\ vareps。这项工作中的重要成分是对不必要连接的失速核心图的系统研究。
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 $σ_{1},\ldots,σ_{r}\in S_{N}$ and evaluating $w\left(σ_{1},\ldots,σ_{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+θ\left(N^{1-π\left(w\right)}\right)$, where $π\left(w\right)$ is the smallest rank of a subgroup $H\le F$ containing $w$ as a non-primitive element. We show that $π\left(w\right)$ plays a role in estimates of all stable characters of symmetric groups. In particular, we show that for all $t\ge2$, the average number of $t$-cycles is $\frac{1}{t}+O\left(N^{-π\left(w\right)}\right)$. As an application, we prove that for every $s$, every $\varepsilon>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}+\varepsilon$ asymptotically almost surely. An important ingredient in this work is a systematic study of not-necessarily connected Stallings core graphs.
