Random permutations acting on $k$--tuples have near--optimal spectral gap for $k=\mathrm{poly}(n)$

Gian-Carlo Rota, On the foundations of combinatorial theory I. theory of Möbius functions , Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2

1964

Earlier work this paper cites.

Uffe Haagerup, An example of a non nuclear C ∗ C^{*} –algebra, which has the metric approximation property , Inventiones Mathematicae 50

1978

Earlier work this paper cites.

Donald Weingarten, Asymptotic behavior of group integrals in the limit of infinite rank , J. Math. Phys. 19

1978

Earlier work this paper cites.

Noga Alon, Eigenvalues and expanders , Combinatorica 6

1986

Earlier work this paper cites.

Alon Nilli, On the second eigenvalue of a graph , Discrete Mathematics 91

1991

Earlier work this paper cites.

Paul Martin and Herbert Saleur, On an algebraic approach to higher dimensional statistical mechanics , Communications in Mathematical Physics 158

1993

Earlier work this paper cites.

Vaughan Frederick Randal Jones, The Potts model and the symmetric group , Subfactors: Proceedings of the Taniguchi Symposium on Operator Algebras (1994), 259–267

1994

Earlier work this paper cites.

Paul Martin, Temperley–Lieb algebras for non–planar statistical mechanics – the partition algebra construction , Journal of Knot Theory and Its Ramifications 03

1994

Earlier work this paper cites.

Alexandru Nica, On the number of cycles of given length of a free word in several random permutations , Random Structures & Algorithms 5

1994

Earlier work this paper cites.

Feng Xu, A random matrix model from two dimensional Yang–Mills theory , Communications in Mathematical Physics 190

1997

Earlier work this paper cites.

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

Earlier work this paper cites.

Benoit Collins, Moments and cumulants of polynomial random variables on unitary groups, the Itzykson–Zuber integral, and free probability , International Mathematics Research Notices 2003

2003

Earlier work this paper cites.

Joel Friedman, Relative expanders or weakly relatively Ramanujan graphs , Duke Mathematical Journal 118

2003

Cited alongside, same era.

Martin Kassabov, Symmetric groups and expander graphs , Inventiones Mathematicae 170

2005

Cited alongside, same era.

Anatoly Vershik and Andrei Okounkov, A new approach to the representation theory of the symmetric groups. II , Journal of Mathematical Sciences 131

2005

Cited alongside, same era.

Daniel T Wise, The coherence of one-relator groups with torsion and the Hanna Neumann conjecture , Bulletin of the London Mathematical Society 37

2005

Cited alongside, same era.

Benoit Collins and Piotr Sniady, Integration with respect to the haar measure on unitary, orthogonal and symplectic group , Comm. Math. Phys. 264

2006

Cited alongside, same era.

Charles Bordenave, A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts , Annales Scientifiques de l’École Normale Supérieure, vol. 4, 2020, pp. 1393–1439

2020

Later among the works it cites.

Sidhanth Mohanty, Ryan O’Donnell, and Pedro Paredes, Explicit near–Ramanujan graphs of every degree , Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020, pp. 510–523

2020

Later among the works it cites.

Benoit Collins, Sho Matsumoto, and Jonathan Novak, The Weingarten calculus , Notices of the American Math. Soc 69

2021

Later among the works it cites.

Liam Hanany and Doron Puder, Word measures on symmetric groups , International Mathematics Research Notices 11

2023

Later among the works it cites.

Doron Puder and Yotam Shomroni, Stable invariants and their role in word measures on groups , preprint, arXiv 2311.17733 (2023)