Random permutations acting on $k$--tuples have near--optimal spectral gap for $k=\mathrm{poly}(n)$
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917038073577472 |
|---|---|
| author | Cassidy, Ewan |
| author_facet | Cassidy, Ewan |
| contents | 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_{n}$--tuples of distinct elements in $[n]$ has a near--optimal spectral gap with high probability, provided $k_{n}\leq n^{\frac{1}{20}-ε}.$ Previously this was known only for $k$--tuples where $k$ is fixed. In fact, we prove the stronger result of strong convergence of random permutations in irreducible representations of quasi--exponential dimension.
Along the way, we give a new bound for the expected stable irreducible character of a random permutation obtained via a word map, showing that $\mathbb{E}\left[χ^μ\left(w(σ_{1},\dots,σ_{r})\right)\right]=O\left(\frac{1}{\dimχ^μ}\right)=O\left(n^{-k}\right)$, where $k$ is the number of boxes outside the first row of the Young diagram $μ,$ solving one aspect of a conjecture of Hanany and Puder. We obtain this bound using an extension of Wise's $w$--cycle conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_13941 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Random permutations acting on $k$--tuples have near--optimal spectral gap for $k=\mathrm{poly}(n)$ Cassidy, Ewan Representation Theory Combinatorics Group Theory Operator Algebras Probability 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_{n}$--tuples of distinct elements in $[n]$ has a near--optimal spectral gap with high probability, provided $k_{n}\leq n^{\frac{1}{20}-ε}.$ Previously this was known only for $k$--tuples where $k$ is fixed. In fact, we prove the stronger result of strong convergence of random permutations in irreducible representations of quasi--exponential dimension. Along the way, we give a new bound for the expected stable irreducible character of a random permutation obtained via a word map, showing that $\mathbb{E}\left[χ^μ\left(w(σ_{1},\dots,σ_{r})\right)\right]=O\left(\frac{1}{\dimχ^μ}\right)=O\left(n^{-k}\right)$, where $k$ is the number of boxes outside the first row of the Young diagram $μ,$ solving one aspect of a conjecture of Hanany and Puder. We obtain this bound using an extension of Wise's $w$--cycle conjecture. |
| title | Random permutations acting on $k$--tuples have near--optimal spectral gap for $k=\mathrm{poly}(n)$ |
| topic | Representation Theory Combinatorics Group Theory Operator Algebras Probability |
| url | https://arxiv.org/abs/2412.13941 |