Random generation with cycle type restrictions

Abstract: We study random generation in the symmetric group when cycle type restrictions are imposed. Given

p i, p i^{'} i n S_{n}

, we prove that

p i

and a random conjugate of

p i^{'}

are likely to generate at least

A_{n}

provided only that

p i

and

p i^{'}

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 l e q d l e q o (n^{1 / 2})

.

This page was built for publication: Random generation with cycle type restrictions