Combinatorics of the Symmetric Group

Abstract

This thesis studies two distinct manifestations of symmetric-group combinatorics in algebra and geometry. In the first, the symmetric group appears as the Weyl group governing decompositions of flag varieties and Grassmannians. In the second, its representation theory motivates the Robinson--Schensted--Knuth correspondence and its connections with crystals, symmetric functions, and positivity.

The first part concerns the Deodhar decomposition of the Grassmannian. Deodhar components refine Richardson and positroid-type decompositions and are indexed combinatorially by Go-diagrams. Each component is isomorphic to $\mathbb{F}^a\times (\mathbb{F}^*)^b$ for some non-negative integers $a$ and $b$. Even though the topology of components is simple, the decomposition is not a stratification, and its closure relations are poorly understood. We introduce the \emph{restricted path parametrization}, an alternative parametrization of Deodhar components constructed directly from the pipe dreams associated with Go-diagrams. This parametrization admits a product factorization that makes changes to the filling of a Go-diagram transparent. We use it to describe Grassmannian duality, to organize the terms appearing in Pl\"ucker coordinates through restricted diagrams, and to establish a family of closure relations between Deodhar components. In particular, we prove a codimension-one closure relation arising from a crossing--uncrossing pair of pipes with consecutive labels.

The second part studies the Robinson--Schensted--Knuth correspondence and its variants from a crystal-theoretic perspective. Crystal structures make representation-theoretic decompositions combinatorially visible and help distinguish insertion algorithms through their compatibility with crystal operators and natural gradings. We focus on the $t=0$ specialization of the Macdonald polynomials: the $q$-Whittaker functions, whose Schur positivity is encoded by the charge statistic and, equivalently, by the energy function on tensor products of Kirillov--Reshetikhin crystals. These crystals are modelled using multiline queues, which admit a combinatorial correspondence analogous to dual RSK. We show that this correspondence is compatible with the decomposition of multiline queues underlying the nonsymmetric and quasisymmetric refinements of the $q$-Whittaker functions. As a consequence, the $t=0$ ASEP polynomials expand positively in Demazure atoms, giving a nonsymmetric refinement of the Schur positivity of the $q$-Whittaker functions.