{
  "id": "2009.00897",
  "version": "v1",
  "published": "2020-09-02T08:36:08.000Z",
  "updated": "2020-09-02T08:36:08.000Z",
  "title": "Word Measures on Symmetric Groups",
  "authors": [
    "Liam Hanany",
    "Doron Puder"
  ],
  "comment": "48 pages, 2 figures. Extended abstract accepted to FPSAC 2020",
  "categories": [
    "math.GR"
  ],
  "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},\\ldots,\\sigma_{r}\\in S_{N}$ and evaluating $w\\left(\\sigma_{1},\\ldots,\\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 \"natural\" families of 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^{-\\pi\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-02T08:36:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20B30",
      "20C30"
    ],
    "keywords": [
      "symmetric group",
      "word measures",
      "average number",
      "not-necessarily connected stallings core graphs",
      "independent uniformly random permutations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 48,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}