Ewens sampling and invariable generation

2016/10/13 by Brito, Gerandy, Fowler, Christopher, Junge, Matthew +1
#12Y05 #60C05 #68W20 #68W30 #68W40 #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Probability (math.PR)

paper · doi:10.48550/arxiv.1610.04212

Abstract

We study the number of random permutations needed to invariably generate the symmetric group, S_n, when the distribution of cycle counts has the strong α-logarithmic property. The canonical example is the Ewens sampling formula, for which the number of k-cycles relates to a conditioned Poisson random variable with mean α/k. The special case α=1 corresponds to uniformly random permutations, for which it was recently shown that exactly four are needed. For strong α-logarithmic measures, and almost every α, we show that precisely \lceil ( 1- αlog 2 )^-1 \rceil permutations are needed to invariably generate S_n. A corollary is that for many other probability measures on S_n no bounded number of permutations will invariably generate S_n with positive probability. Along the way we generalize classic theorems of Erdős, Tehran, Pyber, Luczak and Bovey to permutations obtained from the Ewens sampling formula.

Related

• Random generation under the Ewens distribution
• Involution factorizations of Ewens random permutations
• Representing Random Permutations as the Product of Two Involutions
• The cycle structure of compositions of random involutions
• On statistics of permutations chosen from the Ewens distribution