Math @ Duke

Publications [#340352] of Matthew S Junge
Papers Published
 Brito, G; Fowler, C; Junge, M; Levy, A, Ewens Sampling and Invariable Generation,
Combinatorics, Probability and Computing, vol. 27 no. 6
(November, 2018),
pp. 853891, Cambridge University Press (CUP) [doi]
(last updated on 2019/02/18)
Abstract: © 2018 Cambridge University Press. 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

