## Aldous’s spectral gap conjecture for normal sets

HTML articles powered by AMS MathViewer

- by Ori Parzanchevski and Doron Puder PDF
- Trans. Amer. Math. Soc.
**373**(2020), 7067-7086 Request permission

## 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

- Sinan G. Aksoy, Fan Chung, Michael Tait, and Josh Tobin,
*The maximum relaxation time of a random walk*, Adv. in Appl. Math.**101**(2018), 1–14. MR**3857550**, DOI 10.1016/j.aam.2018.07.002 - Charles Bordenave and Benoît Collins,
*Eigenvalues of random lifts and polynomials of random permutation matrices*, Ann. of Math. (2)**190**(2019), no. 3, 811–875. MR**4024563**, DOI 10.4007/annals.2019.190.3.3 - Emmanuel Breuillard, Ben Green, Robert Guralnick, and Terence Tao,
*Expansion in finite simple groups of Lie type*, J. Eur. Math. Soc. (JEMS)**17**(2015), no. 6, 1367–1434. MR**3353804**, DOI 10.4171/JEMS/533 - Emmanuel Breuillard and Alexander Lubotzky,
*Expansion in simple groups*. arXiv:1807.03879 (2018). - László Babai and Ákos Seress,
*On the degree of transitivity of permutation groups: a short proof*, J. Combin. Theory Ser. A**45**(1987), no. 2, 310–315. MR**894827**, DOI 10.1016/0097-3165(87)90023-9 - László Babai and Ákos Seress,
*On the diameter of permutation groups*, European J. Combin.**13**(1992), no. 4, 231–243. MR**1179520**, DOI 10.1016/S0195-6698(05)80029-0 - Peter J. Cameron,
*Permutation groups*, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999. MR**1721031**, DOI 10.1017/CBO9780511623677 - Filippo Cesi,
*A few remarks on the octopus inequality and Aldous’ spectral gap conjecture*, Comm. Algebra**44**(2016), no. 1, 279–302. MR**3413687**, DOI 10.1080/00927872.2014.975349 - Filippo Cesi,
*On the spectral gap of some Cayley graphs on the Weyl group $W(B_n)$*, Linear Algebra Appl.**586**(2020), 274–295. MR**4027757**, DOI 10.1016/j.laa.2019.10.024 - Pietro Caputo, Thomas M. Liggett, and Thomas Richthammer,
*Proof of Aldous’ spectral gap conjecture*, J. Amer. Math. Soc.**23**(2010), no. 3, 831–851. MR**2629990**, DOI 10.1090/S0894-0347-10-00659-4 - Persi Diaconis,
*Group representations in probability and statistics*, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR**964069** - John D. Dixon,
*The probability of generating the symmetric group*, Math. Z.**110**(1969), 199–205. MR**251758**, DOI 10.1007/BF01110210 - Persi Diaconis and Laurent Saloff-Coste,
*Comparison techniques for random walk on finite groups*, Ann. Probab.**21**(1993), no. 4, 2131–2156. MR**1245303** - William Fulton and Joe Harris,
*Representation theory*, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR**1153249**, DOI 10.1007/978-1-4612-0979-9 - Joel Friedman, Antoine Joux, Yuval Roichman, Jacques Stern, and Jean-Pierre Tillich,
*The action of a few permutations on $r$-tuples is quickly transitive*, Random Structures Algorithms**12**(1998), no. 4, 335–350. MR**1639748**, DOI 10.1002/(SICI)1098-2418(199807)12:4<335::AID-RSA2>3.0.CO;2-U - Joel Friedman,
*A proof of Alon’s second eigenvalue conjecture and related problems*, Mem. Amer. Math. Soc.**195**(2008), no. 910, viii+100. MR**2437174**, DOI 10.1090/memo/0910 - William Fulton,
*Young tableaux*, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry. MR**1464693** - Ziv Greenhut,
*A generation criterion for subsets of special linear groups over finite fields*, 2020. preprint, arXiv:2002.06461. - Shlomo Hoory, Nathan Linial, and Avi Wigderson,
*Expander graphs and their applications*, Bull. Amer. Math. Soc. (N.S.)**43**(2006), no. 4, 439–561. MR**2247919**, DOI 10.1090/S0273-0979-06-01126-8 - Harald A. Helfgott and Ákos Seress,
*On the diameter of permutation groups*, Ann. of Math. (2)**179**(2014), no. 2, 611–658. MR**3152942**, DOI 10.4007/annals.2014.179.2.4 - Harald A. Helfgott, Ákos Seress, and Andrzej Zuk,
*Random generators of the symmetric group: diameter, mixing time and spectral gap*, J. Algebra**421**(2015), 349–368. MR**3272386**, DOI 10.1016/j.jalgebra.2014.08.033 - Camille Jordan,
*Nouvelles recherches sur la limite de transitivité des groupes qui ne contiennent pas le groupe alterné*, J. de Math. Pures et Appliquées**1**(1895), 35–60. - Martin Kassabov,
*Symmetric groups and expander graphs*, Invent. Math.**170**(2007), no. 2, 327–354. MR**2342639**, DOI 10.1007/s00222-007-0065-y - Michael Larsen and Aner Shalev,
*Characters of symmetric groups: sharp bounds and applications*, Invent. Math.**174**(2008), no. 3, 645–687. MR**2453603**, DOI 10.1007/s00222-008-0145-7 - Alexander Lubotzky,
*Expander graphs in pure and applied mathematics*, Bull. Amer. Math. Soc. (N.S.)**49**(2012), no. 1, 113–162. MR**2869010**, DOI 10.1090/S0273-0979-2011-01359-3 - I. G. Macdonald,
*Symmetric functions and Hall polynomials*, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science Publications. MR**1354144** - Laurent Saloff-Coste,
*Random walks on finite groups*, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 263–346. MR**2023654**, DOI 10.1007/978-3-662-09444-0_{5}

## 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.
- © Copyright 2020 American Mathematical Society
- 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
- MathSciNet review: 4155200