We study random generation in the symmetric group when cycle type restrictions are imposed. Given , we prove that and a random conjugate of are likely to generate at least provided only that and have not too many fixed points and not too many -cycles. As an application, we investigate the following question: For which positive integers should we expect two random elements of order to generate ? Among other things, we give a positive answer for any having any divisor in the range .
Revised:
Accepted:
Published online:
Keywords: symmetric group, random generation.
@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 = {http://www.numdam.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 SP - 1 EP - 25 VL - 4 IS - 1 PB - MathOA foundation UR - http://www.numdam.org/articles/10.5802/alco.149/ DO - 10.5802/alco.149 LA - en ID - ALCO_2021__4_1_1_0 ER -
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. http://www.numdam.org/articles/10.5802/alco.149/
[1] The probability of generating the symmetric group, J. Combin. Theory Ser. A, Volume 52 (1989) no. 1, pp. 148-153 | DOI | MR | Zbl
[2] 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] On fixed points of permutations, J. Algebraic Combin., Volume 28 (2008) no. 1, pp. 189-218 | DOI | MR | Zbl
[4] The probability of generating the symmetric group, Math. Z., Volume 110 (1969), pp. 199-205 | DOI | MR | Zbl
[5] Permutations contained in transitive subgroups, Discrete Anal. (2016), 12, 34 pages | DOI | MR | Zbl
[6] Analytic combinatorics, Cambridge University Press, Cambridge, 2009, xiv+810 pages | DOI | MR | Zbl
[7] 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] Classical groups, probabilistic methods, and the -generation problem, Ann. of Math. (2), Volume 144 (1996) no. 1, pp. 77-125 | DOI | MR | Zbl
[9] 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] On random generation of the symmetric group, Combin. Probab. Comput., Volume 2 (1993) no. 4, pp. 505-512 | DOI | MR | Zbl
[11] 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: