Symmetric Group Generation and Shuffle Permutations

Fabio Guerinoni
Department of Mathematics
Virginia State University

Shuffle permutations have applications that vary from magic card tricks to the design of parallel sorting networks. Their study may touch a number of areas: Markov chains, random walks, statistics, asymptotics and algorithmic group theory. In this talk, we introduce the basics and briefly address how the subject is related to some of the above. In particular, we outline the complex Schreier-Sims algorithm and its importance in solving polynomially many problems in permutation groups.

The last part of the talks deal with generation. A well-known theorem shows that, probabilistically, the symmetric group can be very easily generated using two random permutations. We show techniques and results when ``random'' is replaced by ``shuffle.''

Back to seminar homepage