On the diameter of the symmetric group: polynomial bounds

László Babai, Robert Beals, Ákos Seress

Type: Article

Publication Date: 2004-01-11

Citations: 30

DOI: https://doi.org/10.5555/982792.982956

View Publication

Locations

Symposium on Discrete Algorithms - View

Similar Works

Action	Title	Year	Authors
+	Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group	2005	László Babai Thomas P. Hayes
+	Bounds on the diameter of Cayley graphs of the symmetric group	2012	John Bamberg Nick Gill Thomas Hayes H. A. Helfgott Ákos Seress Pablo Spiga
+	Bounds on the diameter of Cayley graphs of the symmetric group	2012	John Bamberg Nick Gill Thomas P. Hayes H. A. Helfgott Ákos Seress Pablo Spiga
+ PDF Chat	Bounds on the diameter of Cayley graphs of the symmetric group	2013	John Bamberg Nick Gill Thomas P. Hayes H. A. Helfgott Ákos Seress Pablo Spiga
+	On the diameter of cayley graphs of the symmetric group	1988	László Babai Ákos Seress
+	On the diameter of permutation groups	2011	H. A. Helfgott Ákos Seress
+	On the diameter of permutation groups	2011	H. A. Helfgott Ákos Seress
+	On the diameter of permutation groups	1992	László Babai Ákos Seress
+	Random generators of the symmetric group: diameter, mixing time and spectral gap	2013	H. A. Helfgott Ákos Seress Andrzej Żuk
+	Random generators of the symmetric group: diameter, mixing time and spectral gap	2013	H. A. Helfgott Ákos Seress Andrzej Żuk
+ PDF Chat	On the diameter of permutation groups	2014	H. A. Helfgott Ákos Seress
+	Random generators of the symmetric group: Diameter, mixing time and spectral gap	2014	H. A. Helfgott Ákos Seress Andrzej Żuk
+	On The Diameter of Pancake Graphs	2022	V R Harigovind Pramod P Nair
+	On the proportion of elements of prime order in finite symmetric groups	2022	Cheryl E. Praeger Enoch Suleiman
+	Girth, words and diameter	2019	Martin W. Liebeck Aner Shalev
+ PDF Chat	Girth, words and diameter	2019	Martin W. Liebeck Aner Shalev
+	The probability of generating the symmetric group when one of the generators is random	2006	László Babai Thomas P. Hayes
+	On the length of subgroup chains in the symmetric group	1986	László Babai
+ PDF Chat	Groupoid Cardinality and Random Permutations	2024	John C. Baez
+	On the diameter of Eulerian orientations of graphs	2006	László Babai

Works That Cite This (28)

Action	Title	Year	Authors
+ PDF Chat	Growth and expansion in algebraic groups over finite fields	2019	H. A. Helfgott
+ PDF Chat	Bounds on the diameter of Cayley graphs of the symmetric group	2013	John Bamberg Nick Gill Thomas P. Hayes H. A. Helfgott Ákos Seress Pablo Spiga
+	Short expressions of permutations as products and cryptanalysis of the Algebraic Eraser	2012	Arkadius Kalka Mina Teicher Boaz Tsaban
+	Random generators of the symmetric group: Diameter, mixing time and spectral gap	2014	H. A. Helfgott Ákos Seress Andrzej Żuk
+	None	2009	Alex Gamburd Shlomo Hoory Mehrdad Shahshahani Aner Shalev Bálint Virág
+ PDF Chat	Growth in groups: ideas and perspectives	2015	H. A. Helfgott
+ PDF Chat	Babai’s conjecture for high-rank classical groups with random generators	2021	Sean Eberhard Urban Jezernik
+	Babai's conjecture for high-rank classical groups with random generators	2020	Sean Eberhard Urban Jezernik
+	Diameter of Cayley graphs of SL(n,p) with generating sets containing a transvection	2020	Zoltán Halasi
+	Growth in groups: ideas and perspectives	2013	H. A. Helfgott

Works Cited by This (12)

Action	Title	Year	Authors
+	Handbuch der Lehre von der Verteilung der Primzahlen	1911	Edmund Landau
+	On the diameter of cayley graphs of the symmetric group	1988	László Babai Ákos Seress
+	Bounds for eigenvalues of certain stochastic matrices	1981	H. J. Landau Andrew Odlyzko
+	The Probability that some Power of a Permutation has Small Degree	1980	J. D. Bovey
+	Computation with permutation groups	1971	Charles C. Sims
+	On the Diameter of Random Cayley Graphs of the Symmetric Group	1992	László Babai Gábor Hetyei
+	The probability of generating the symmetric group	1989	László Babai
+	On the diameter of permutation groups	1992	László Babai Ákos Seress
+	On the length of subgroup chains in the symmetric group	1986	László Babai
+ PDF Chat	Polynomial-time algorithms for permutation groups	1980	Merrick L. Furst John E. Hopcroft Eugene M. Luks