Ewens Sampling and Invariable Generation. (12th April 2018)

• Record Type: Journal Article
• Authors: BRITO, GERANDY; FOWLER, CHRISTOPHER; JUNGE, MATTHEW; LEVY, AVI
• Is Part Of: Combinatorics, probability and computing. Volume 27:Number 6(2018)
• Page Start: 853
• Page End: 891
• Publication Date: 2018-04-12
• Subjects: Primary 60C05, -- Secondary 12Y05, -- 68W20, -- 68W30, -- 68W40; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S096354831800007X
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : We study the number of random permutations needed to invariably generate the symmetric group Sn when the distribution of cycle counts has the strong α-logarithmic property. The canonical example is the Ewens sampling formula, for which the special case α = 1 corresponds to uniformly random permutations. For strong α-logarithmic measures and almost every α, we show that precisely ⌈(1−αlog2) −1 ⌉ permutations are needed to invariably generate Sn with asymptotically positive probability. A corollary is that for many other probability measures on Sn no fixed number of permutations will invariably generate Sn with positive probability. Along the way we generalize classic theorems of Erdős, Tehran, Pyber, Łuczak and Bovey to permutations obtained from the Ewens sampling formula.