Permutation, Coagulation, and Fragmentation

Tom Halverson
Macalester College

We will begin by looking at a random walk on permutations using transpositions — this can be viewed as a way of shuffling cards by repeatedly swapping pairs of them. We will ask the questions: do we get random permutations this way (i.e., do the cards get shuffled?) and, if so, how fast do we get random (i.e., how many shuffles are needed)? Our analysis will use a ideas from linear algebra, discrete math, probability, and group theory.

We will then move on to a problem that Owen Anderson (Mac '08) and I examined in the summer of 2006. This involves a random walk on set partitions using operations that "coagulate" and "fragment" these partitions. We ask the same quesions: how random? how fast? And we get some very surprising answers that make connections to alternating sign matrices. Most of this talk will accessible to a general audience, especially to those who have thought about eigenvalues. We also will make some forays into the world of abstract algebra.

The transition diagram for a coagulation-fragmention walk on planar partitions of {1,2,3}.