Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Aldous’s spectral gap conjecture for normal sets


Authors: Ori Parzanchevski and Doron Puder
Journal: Trans. Amer. Math. Soc. 373 (2020), 7067-7086
MSC (2010): Primary 20C30, 05C81; Secondary 05C50, 20B20, 20B30, 60B15
DOI: https://doi.org/10.1090/tran/8155
Published electronically: July 29, 2020
MathSciNet review: 4155200
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $S_{n}$ denote the symmetric group on $n$ elements, and let $\Sigma \subseteq S_{n}$ be a symmetric subset of permutations. Aldous’s spectral gap conjecture, proved by Caputo, Liggett, and Richthammer [J. Amer. Math. Soc. 23 (2010), no. 3, 831–851], 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 [Invent. Math. 174 (2008), no. 3, 645–687], 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.


References [Enhancements On Off] (What's this?)

References

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20C30, 05C81, 05C50, 20B20, 20B30, 60B15

Retrieve articles in all journals with MSC (2010): 20C30, 05C81, 05C50, 20B20, 20B30, 60B15


Additional Information

Ori Parzanchevski
Affiliation: Einstein School of Mathematics, Edmond J. Safra Campus, The Hebrew University, Jerusalem, Israel
MR Author ID: 879748
ORCID: 0000-0003-1596-215X
Email: parzan@math.huji.ac.il

Doron Puder
Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel
MR Author ID: 903080
ORCID: 0000-0003-2793-7525
Email: doronpuder@gmail.com

Received by editor(s): July 1, 2018
Received by editor(s) in revised form: December 31, 2019, and January 6, 2020
Published electronically: July 29, 2020
Additional Notes: This research was supported by the Israel Science Foundation, ISF grant 1031/17 awarded to the first author and ISF grant 1071/16 awarded to the second author.
Article copyright: © Copyright 2020 American Mathematical Society