ALGEBRAIC COMBINATORICS

no. 1
Random generation with cycle type restrictions
Eberhard, Sean1; Garzoni, Daniele2
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
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:
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
License: CC-BY 4.0
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
SP  - 1
EP  - 25
VL  - 4
IS  - 1
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/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://alco.centre-mersenne.org/articles/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 (2,3)-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: