Speaker: Erik Slivken, Paris VII
Date and time: Thursday, September 27, 4–5 pm
Location: Phillips 110
Abstract: We begin with a simple sorting algorithm on a randomly ordered stack of cards labeled 1 through n. If the first card is labeled k, slide that card into the kth position. Repeat until the first card is a 1. This algorithm induces a directed forest structure on the set of permutations. The local limit of this structure converges to a random tree which itself can be constructed directly from a sequence of Poisson point processes. We are able to compute a variety of statistics related to this tree, such as the distribution of the longest and shortest path to a leaf, or its expected size. We also study generalizations of this random tree.