ALGEBRAIC COMBINATORICS

no. 1

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 π,π ′ ∈S n , we prove that π and a random conjugate of π ′ are likely to generate at least A n provided only that π and π ′ 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≤d≤o(n 1/2 ).

Received: 2019-04-29
Revised: 2020-06-25
Accepted: 2020-09-02
Published online: 2021-02-16
DOI: https://doi.org/10.5802/alco.149
Classification: 20B30,  20P05
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 = {https://alco.centre-mersenne.org/item/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/item/ALCO_2021__4_1_1_0/

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

[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 2273979 | Zbl 1123.20003

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

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

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

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

[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 | Article | MR 929529 | Zbl 0647.20005

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

[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 | Article | MR 2058457 | Zbl 1068.20052

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

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