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