Skip navigation
Please use this identifier to cite or link to this item:
Title: Stack-Sorting and Beyond
Authors: Defant, Colin
Advisors: Alon, Noga
Contributors: Mathematics Department
Keywords: binary plane tree
free probability
valid hook configuration
Subjects: Mathematics
Issue Date: 2022
Publisher: Princeton, NJ : Princeton University
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.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Mathematics

Files in This Item:
File Description SizeFormat 
Defant_princeton_0181D_14096.pdf4.19 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.