Stack-Sorting and Beyond

Abstract

In 1990, West initiated an extensive investigation of the stack-sorting map, a deterministic version of Knuth's stack-sorting machine that acts on permutations. At first sight, this map appears complicated and messy; for many years, it was studied as an isolated topic without many connections to other parts of mathematics. One of the primary goals of this thesis is to demonstrate that the stack-sorting map is actually a very natural object of study with fascinating connections to other mathematical areas. Throughout our exploration of the stack-sorting map, we will encounter cumulants in noncommutative probability theory; special convex polytopes called \emph{fertilitopes}; intervals in special posets; binary plane trees; several questions about symmetry, unimodality, log-concavity, and real-rootedness; and many interesting combinatorial sequences. We will also formulate natural generalizations of stack-sorting for arbitrary Coxeter groups. The new techniques that we introduce will allow us to answer several old questions, reprove and generalize known results, prove completely new theorems, and formulate entirely new questions. Much of our attention will be directed toward \emph{valid hook configurations}, which are new combinatorial objects that allow us to count the preimages of an arbitrary permutation under the stack-sorting map. Very surprisingly, valid hook configurations also arise in a formula in noncommutative probability theory that converts from free cumulants to classical cumulants. This allows us to use free probability theory to prove deep facts about the stack-sorting map and its generalizations. We also initiate a theory of \emph{troupes}, which are sets of colored binary plane trees that are closed under certain operations. Troupes provide a broad framework where many results about stack-sorting can be generalized uniformly. On the other hand, we will also show how stack-sorting and its generalizations can be used, along with troupes and valid hook configurations, to prove a striking relationship between free and classical cumulants. Troupes and valid hook configurations help to illuminate the delightful combinatorial structure lurking beneath the surface of the stack-sorting map; our hope is that some readers will see this hidden structure, find inspiration to answer some of the new questions that we formulate, and ask new questions of their own.