Structure in stack-sorting

Colin Defant, Princeton University
Fine Hall 110

The study of permutation patterns, an enormous area of research in modern combinatorics, began with Knuth’s analysis of a certain “stack-sorting algorithm” in 1968. In his 1990 PhD. thesis, West investigated a deterministic variant of Knuth’s algorithm, which we can view as a map s that sends permutations to permutations. He defined the fertility of a permutation to be the number of preimages of that permutation under s. We will describe a colorful method for computing the fertility of any permutation. Applications of this method allow us to connect the stack-sorting map with free probability theory, set partitions, acyclic orientations of graphs, lattice paths, and several well-studied sequences. Another interesting application shows that the set of nonnegative integers that arise as fertilities of permutations is closed under multiplication. We will also discuss tortoise and hare, two operators on words that extend the stack-sorting map.