CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
Robin Pemantle
UPenn
Title: Permutations and sumsets of a random Poisson-Zipf set

Abstract: Let M be a random set of integers greater than 1, containing each integer n independently with probability 1/n. Let S(M) be the sumset of M, that is, the set of all sums of subsets of M. How many independent copies of S must one intersect in order to obtain a finite set?

This problem arises from the analysis of an algorithm in computational Galois theory. The relevant question there is, how many random permutations chosen uniformly from the symmetric group Sn must you sample before there is at least an epsilon probability that these permutations generate Sn even when an adversary replaces each one with a conjugate (another permutation of the same cycle type)?

Dixon showed in 1992 that C (log n)1/2 sufficed, and conjectured that O(1) was good enough, which was proved shortly thereafter by Luczak and Pyber. Their constant was 2100 has not been improved until now, though various guesses have been made as to the actual number: 13, 12, 5, 4. We show in fact that 4 permutations suffice (equivalently, four copies of S have finite intersection).

Joint work with Yuval Peres and Igor Rivin

Date: Thursday, April 30, 2015
Time: 3:30 pm
Location: Wean Hall 8220