# ALGEBRAIC COMBINATORICS

Random generation with cycle type restrictions
Algebraic Combinatorics, Volume 4 (2021) no. 1, pp. 1-25.

We study random generation in the symmetric group when cycle type restrictions are imposed. Given $\pi ,{\pi }^{\prime }\in {S}_{n}$, we prove that $\pi$ and a random conjugate of ${\pi }^{\prime }$ are likely to generate at least ${A}_{n}$ provided only that $\pi$ and ${\pi }^{\prime }$ have not too many fixed points and not too many $2$-cycles. As an application, we investigate the following question: For which positive integers $m$ should we expect two random elements of order $m$ to generate ${A}_{n}$? Among other things, we give a positive answer for any $m$ having any divisor $d$ in the range $3\le d\le o\left({n}^{1/2}\right)$.

Revised:
Accepted:
Published online:
DOI: 10.5802/alco.149
Classification: 20B30,  20P05
Keywords: symmetric group, random generation.
Eberhard, Sean 1; Garzoni, Daniele 2

1 Centre for Mathematical Sciences Wilberforce Road Cambridge CB3 0WB, U.K.
2 Dipartimento di Matematica “Tullio Levi–Civita” Università degli Studi di Padova Padova, Italy
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{ALCO_2021__4_1_1_0,
author = {Eberhard, Sean and Garzoni, Daniele},
title = {Random generation with cycle type restrictions},
journal = {Algebraic Combinatorics},
pages = {1--25},
publisher = {MathOA foundation},
volume = {4},
number = {1},
year = {2021},
doi = {10.5802/alco.149},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.149/}
}
TY  - JOUR
AU  - Eberhard, Sean
AU  - Garzoni, Daniele
TI  - Random generation with cycle type restrictions
JO  - Algebraic Combinatorics
PY  - 2021
DA  - 2021///
SP  - 1
EP  - 25
VL  - 4
IS  - 1
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.149/
UR  - https://doi.org/10.5802/alco.149
DO  - 10.5802/alco.149
LA  - en
ID  - ALCO_2021__4_1_1_0
ER  - 
%0 Journal Article
%A Eberhard, Sean
%A Garzoni, Daniele
%T Random generation with cycle type restrictions
%J Algebraic Combinatorics
%D 2021
%P 1-25
%V 4
%N 1
%I MathOA foundation
%U https://doi.org/10.5802/alco.149
%R 10.5802/alco.149
%G en
%F ALCO_2021__4_1_1_0
Eberhard, Sean; Garzoni, Daniele. Random generation with cycle type restrictions. Algebraic Combinatorics, Volume 4 (2021) no. 1, pp. 1-25. doi : 10.5802/alco.149. https://alco.centre-mersenne.org/articles/10.5802/alco.149/

[1] Babai, László The probability of generating the symmetric group, J. Combin. Theory Ser. A, Volume 52 (1989) no. 1, pp. 148-153 | DOI | MR | Zbl

[2] Babai, László; Hayes, Thomas P. The probability of generating the symmetric group when one of the generators is random, Publ. Math. Debrecen, Volume 69 (2006) no. 3, pp. 271-280 | MR | Zbl

[3] Diaconis, Persi; Fulman, Jason; Guralnick, Robert On fixed points of permutations, J. Algebraic Combin., Volume 28 (2008) no. 1, pp. 189-218 | DOI | MR | Zbl

[4] Dixon, John D. The probability of generating the symmetric group, Math. Z., Volume 110 (1969), pp. 199-205 | DOI | MR | Zbl

[5] Eberhard, Sean; Ford, Kevin; Koukoulopoulos, Dimitris Permutations contained in transitive subgroups, Discrete Anal. (2016), Paper no. 12, 34 pages | DOI | MR | Zbl

[6] Flajolet, Philippe; Sedgewick, Robert Analytic combinatorics, Cambridge University Press, Cambridge, 2009, xiv+810 pages | DOI | MR | Zbl

[7] Liebeck, Martin W.; Praeger, Cheryl E.; Saxl, Jan On the O’Nan–Scott theorem for finite primitive permutation groups, J. Austral. Math. Soc. Ser. A, Volume 44 (1988) no. 3, pp. 389-396 | DOI | MR | Zbl

[8] Liebeck, Martin W.; Shalev, Aner Classical groups, probabilistic methods, and the $\left(2,3\right)$-generation problem, Ann. of Math. (2), Volume 144 (1996) no. 1, pp. 77-125 | DOI | MR | Zbl

[9] Liebeck, Martin W.; Shalev, Aner Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks, J. Algebra, Volume 276 (2004) no. 2, pp. 552-601 | DOI | MR | Zbl

[10] Łuczak, Tomasz; Pyber, László On random generation of the symmetric group, Combin. Probab. Comput., Volume 2 (1993) no. 4, pp. 505-512 | DOI | MR | Zbl

[11] Shalev, Aner Random generation of simple groups by two conjugate elements, Bull. London Math. Soc., Volume 29 (1997) no. 5, pp. 571-576 | DOI | MR | Zbl

Cited by Sources: