Random generation with cycle type restrictions

Sean Eberhard; Daniele Garzoni

doi:10.5802/ALCO.149

Random generation with cycle type restrictions

Sean Eberhard, Daniele Garzoni

Research output: Contribution to journal › Article › peer-review

31 Downloads (Pure)

Abstract

We study random generation in the symmetric group when cycle type restrictions are imposed. Given π, π0 2 Sn, we prove that π and a random conjugate of π0 are likely to generate at least An provided only that π and π0 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 An? Among other things, we give a positive answer for any m having any divisor d in the range 3 ≤ d ≤ o(n1/2).

Original language	English
Pages (from-to)	1-25
Number of pages	25
Journal	Algebraic Combinatorics
Volume	4
Issue number	1
DOIs	https://doi.org/10.5802/ALCO.149
Publication status	Published - 16 Feb 2021
Externally published	Yes

Bibliographical note

Publisher Copyright:
© The journal and the authors, 2021.

Keywords

Random generation
Symmetric group

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.5802/ALCO.149Licence: CC BY

Random generation with cycle type restrictions
Copyright 2021 the authors. This is an open access article published under a Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium, provided the author and source are cited.
Final published version, 684 KBLicence: CC BY

Cite this

@article{2043d88c177d4d32b9a9cdd5f7bf593e,

title = "Random generation with cycle type restrictions",

abstract = "We study random generation in the symmetric group when cycle type restrictions are imposed. Given π, π0 2 Sn, we prove that π and a random conjugate of π0 are likely to generate at least An provided only that π and π0 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 An? Among other things, we give a positive answer for any m having any divisor d in the range 3 ≤ d ≤ o(n1/2).",

keywords = "Random generation, Symmetric group",

author = "Sean Eberhard and Daniele Garzoni",

note = "Publisher Copyright: {\textcopyright} The journal and the authors, 2021.",

year = "2021",

month = feb,

day = "16",

doi = "10.5802/ALCO.149",

language = "English",

volume = "4",

pages = "1--25",

journal = "Algebraic Combinatorics",

issn = "2589-5486",

publisher = "Centre Mersenne",

number = "1",

}

TY - JOUR

T1 - Random generation with cycle type restrictions

AU - Eberhard, Sean

AU - Garzoni, Daniele

PY - 2021/2/16

Y1 - 2021/2/16

N2 - We study random generation in the symmetric group when cycle type restrictions are imposed. Given π, π0 2 Sn, we prove that π and a random conjugate of π0 are likely to generate at least An provided only that π and π0 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 An? Among other things, we give a positive answer for any m having any divisor d in the range 3 ≤ d ≤ o(n1/2).

AB - We study random generation in the symmetric group when cycle type restrictions are imposed. Given π, π0 2 Sn, we prove that π and a random conjugate of π0 are likely to generate at least An provided only that π and π0 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 An? Among other things, we give a positive answer for any m having any divisor d in the range 3 ≤ d ≤ o(n1/2).

KW - Random generation

KW - Symmetric group

U2 - 10.5802/ALCO.149

DO - 10.5802/ALCO.149

M3 - Article

AN - SCOPUS:85102612649

SN - 2589-5486

VL - 4

SP - 1

EP - 25

JO - Algebraic Combinatorics

JF - Algebraic Combinatorics

IS - 1

ER -

Random generation with cycle type restrictions

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this