Aldous' Spectral Gap Conjecture for Normal Sets
| Autor: | Doron Puder, Ori Parzanchevski |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Conjecture
Cayley graph Applied Mathematics General Mathematics 20c30 (primary) 20c15 05c81 05c50 20B20 20B30 60B15 60J10 60k35 (secondary) Probability (math.PR) Symmetric set Group Theory (math.GR) State (functional analysis) Type (model theory) Combinatorics Conjugacy class Symmetric group FOS: Mathematics Mathematics - Combinatorics Spectral gap Combinatorics (math.CO) Mathematics - Group Theory Mathematics - Probability Mathematics |
| Popis: | Let $S_n$ denote the symmetric group on $n$ elements, and $\Sigma\subseteq S_{n}$ a symmetric subset of permutations. Aldous' spectral gap conjecture, proved by Caputo, Liggett and Richthammer [arXiv:0906.1238], states that if $\Sigma$ is a set of transpositions, then the second eigenvalue of the Cayley graph $\mathrm{Cay}\left(S_{n},\Sigma\right)$ is identical to the second eigenvalue of the Schreier graph on $n$ vertices depicting the action of $S_{n}$ on $\left\{ 1,\ldots,n\right\}$. Inspired by this seminal result, we study similar questions for other types of sets in $S_{n}$. Specifically, we consider normal sets: sets that are invariant under conjugation. Relying on character bounds due to Larsen and Shalev [2008], we show that for large enough $n$, if $\Sigma\subset S_{n}$ is a full conjugacy class, then the second eigenvalue of $\mathrm{Cay}\left(S_{n},\Sigma\right)$ is roughly identical to the second eigenvalue of the Schreier graph depicting the action of $S_{n}$ on ordered $4$-tuples of elements from $\left\{ 1,\ldots,n\right\}$. We further show that this type of result does not hold when $\Sigma$ is an arbitrary normal set, but a slightly weaker one does hold. We state a conjecture in the same spirit regarding an arbitrary symmetric set $\Sigma\subset S_{n}$, which yields surprisingly strong consequences. Comment: 18 pages, 4 tables, journal version, improved exposition, to appear in TAMS (Transactions of the American Mathematical Society) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|