Prelude to an Oral Exam
Cruz Godar
Made with 
and 
Background
A partition of an integer $n$ is a sequence $(a_1, a_2, ... )$ of decreasing nonnegative integers $a_i$ with $\sum_i a_i = n$.
Ex: $(5, 3, 2, 2, 1, 0, 0, ...)$ is a partition of $13$.
The Young diagram corresponding to a partition $(a_i)$ is the set $\{(i, j) \in \mathbb{N}^2 \mid 1 \leq j \leq a_i\}$.
We usually treat these as top-left-justified sets of squares in a grid, so that $a_i$ is the length of row $i$.
Ex: the Young diagram of $(5, 3, 2, 2, 1, 0, 0, ...)$.
Plane Partitions
A plane partition is a placement of nonnegative integers into a Young diagram, such that the rows and columns weakly decrease. We can also think of them as a stacks of boxes, with each number indicating how many boxes are stacked on that square.
The weight of a plane partition $\pi$, written $|\pi|$, is just the sum of its entries, or equivalently the total number of boxes stacked.
If we require the rows and columns of a plane partition to weakly increase rather than decrease, the resulting object is called a reverse plane partition, or RPP.
Ex: a plane partition of weight $33$.
Hooks and Hook Lengths
The hook corresponding to a box in a plane partition is the right-angled collection of boxes directly above and to the left of it. The hook length $h(i, j)$ of a box is the total number of boxes in its hook, and the corner box $(i, j)$ is called the pivot of the hook.
In an RPP, the direction of hooks is reserved along with the inequalities, and they extend down and right instead.
Ex: $h(2, 1) = 5$ in this RPP.
A Generating Function for RPPs
A famous result (due to Stanley in his Ph.D. thesis) expresses the generating function for RPPs of shape $\lambda$ as a product involving hook lengths:
Thm: $\displaystyle \sum_\pi q^{|\pi|} = \prod_{(i, j) \in \lambda} \frac{1}{1 - q^{h(i, j)}},$
where the sum is taken over all RPPs $\pi$ of shape $\lambda$. Since boxes and hooks are in bijection, the combinatorial interpretation is that RPPs of shape $\lambda$ are in bijection with multi-sets of hooks in a diagram of shape $\lambda$.
Hillman-Grassl
The first bijective proof of the hook length formula is due to Hillman and Grassl in 1975. Given a multi-set of hooks, it is not possible to place them unmodified to construct an RPP: for example, with $\lambda = (2, 2)$, the hook with pivot $(1, 1)$ makes the tableau
$\begin{array}{cc}1 & 1 \\ 1 & 0\end{array}$
which isn’t a valid RPP.
Zigzag Paths
The Hillman-Grassl map decomposes RPPs into zigzag paths instead of hooks. A zigzag path begins at the leftmost nonzero entry at the bottom of its column. It moves up if the entries are equal and right otherwise, until it can no longer move.
The pivot of a zigzag path is the entry with the path’s starting column and ending row.
Every nonzero RPP has a unique zigzag path, and decrementing its entries preserves the RPP inequalities. Critically, every zigzag path has length equal to its pivot’s hook length.
The Hillman-Grassl map $\operatorname{HG}$ is a bijection between RPPs and multisets of hooks. It operates on an RPP by decrementing its zigzag path, finding the zigzag path of the resulting RPP and decrementing it, and so on, until eventually the RPP has weight zero. At each step, we record the corresponding hook formed.
The removal of a zigzag path is an invertible operation, and it can be shown that the generated sequence of pivots respects a reverse lexicographic ordering, so given a multiset of pivots, the inverse map $\operatorname{HG}^{-1}$ is well-defined.
Since hooks are in bijection with pivots, we can concisely represent the multiset of hooks as a tableau of shape $\lambda$, weighted by hook length.
Pak
In 2002, Igor Pak found a different bijection between RPPs and multisets of hooks. In contrast to Hillman-Grassl, Pak’s bijection operates on the level of boxes rather than hooks.
For ease of notation, let $\lambda$ be a partition and $x \in \lambda$ (i.e. a box in the Young diagram), and define $\mathbf{n}x$, $\mathbf{s}x$, $\mathbf{e}x$, and $\mathbf{w}x$ to be the boxes above, below, right, and left of $x$, respectively.
Given an RPP $\pi$, select an outer corner of the diagram and call it $y$. For every $x$ in the same diagonal as $y$ other than $y$ itself, define the toggle of $\pi(x)$ to be
$\displaystyle \pi'(x) = \max(\pi(\mathbf{n}x), \pi(\mathbf{w}x)) + \min(\pi(\mathbf{s}x), \pi(\mathbf{e}x)) - \pi(x).$
In other words, the toggle of $\pi(x)$ is the max of the adjacent entries smaller than it, plus the min of the adjacent entries larger than it, minus itself.
We now replace $\pi(x)$ with $\pi'(x)$ for all $x$ in the diagonal, excluding $y$.
We handle the outer corner $y$ differently: it is completely removed from $\pi$, and the value
$\displaystyle \pi(y) - \max(\pi(\mathbf{n}y), \pi(\mathbf{w}y)),$
which is how much larger $\pi(y)$ is than strictly necessary, is stored in a tableau at the same location. The shape of the RPP is now one box smaller, and we repeat the previous procedure, choosing a new outer corner, until the RPP is empty.
The RPP in the next animation has been rotated 180$^\circ$, so outer corners are in the top-left. For clarity, toggled corners remain in the same diagram, but they are given color.
It can be shown that the order in which corners are chosen does not impact the final result of Pak, and (more easily) that entries in the output tableau contribute weight equal to their hook length.
Toggling a non-corner entry is an involution, and knowing the entry recorded to the tableau from a toggled corner lets us recover the corner’s entry in the RPP. Therefore, the inverse bijection is well-defined.
While the algorithm is simple enough, the fact that it outputs multisets of hooks seems to hint at a description closer in style to Hillman-Grassl.
Sulzgruber
In 2017, Robin Sulzgruber found exactly that: an equivalent formulation of Pak’s bijection that removes one hook at a time.
Given a partition $\lambda$, we divide its Young diagram into four regions:
$\mathcal{O}$ consists of diagonals ending in an outer corner.
$\mathcal{I}$ consists of diagonals ending in an inner corner.
$\mathcal{A}$ consists of diagonals ending in a horizontal edge.
$\mathcal{B}$ consists of diagonals ending in a vertical edge.
Given an RPP $\pi$, we define the set of candidates $C(\pi)$ to be the cells $x \in \mathcal{O}$ with $\pi(\mathbf{w}u) < \pi(u)$, along with the cells $x \in \mathcal{A}$ with $\pi(\mathbf{w}u) < \pi(u) > \pi(\mathbf{n}u)$.
We select the minimum candidate $x$ with respect to content order — that is, whose diagonal is as north-east as possible, with preference within a diagonal given to the south-east end. With $x$ as a starting position, we build a path as follows:
If the current cell $x$ belongs to $\mathcal{O} \cup \mathcal{B}$ and $\pi(\mathbf{nx}) = \pi(x)$, we move one cell north. Otherwise, we move cell east unless that move leaves the diagram, in which case we stop. As with Hillman-Grassl, we decrement this path, store its pivot in a tableau, and repeat until the RPP is empty.
Incredibly, Pak and Sulzgruber’s maps produce identical results despite wildly differing descriptions. We refer to the map collectively as $\operatorname{PS}$.
There is a surprising connection between $\operatorname{PS}$ and the $\operatorname{RSK}$ algorithm. Given a square tableau $T$, the diagonals of $\operatorname{PS}^{-1}(T)$ give the shapes of restrictions of $P$ and $Q$ in $(P, Q) = \operatorname{RSK}(T)$.
Garver-Patrias
This result is stated in a different but equivalent manner in a paper by Garver and Patrias. Given a Young diagram of shape $\lambda$, we first label each box in reading order.
Given a tableau $T$ of shape $\lambda$, which is equivalent to a multiset of hooks, we write them in the order the Sulzgruber algorithm inserts them, and then read off the labels of their pivots to form a word $w$. In this example, $w = 145539$.
For each diagonal $d$, we form the subword $w_d$ of $w$ by selecting only the labels whose hooks intersect diagonal $d$.
Here, $w_{-2} = 14$, $w_{-1} = 1455$, $w_0 = 145539$, $w_1 = 14553$, and $w_2 = 13$.
We now run $\operatorname{RSK}$ on each $w_d$ and store the shape of the resulting tableaux in the corresponding diagonal.
For example, the tableau $P$ in $\operatorname{RSK}(w_1) = \operatorname{RSK}(14355)$ is
$\displaystyle\begin{array}{cccc}1 & 3 & 5 & 5 \\ 4\end{array},$
so we place the partition $(4, 1)$ into the diagonal $d = 1$ (in reverse order).
Thm: This process is equivalent to $\operatorname{PS}$.
We can describe $\operatorname{HG}$ in an identical way by changing the labeling order to be right to left, top to bottom, and then changing the hook ordering to match $\operatorname{HG}$’s insertion order. The result is a much more clear connection between the two bijections.
What’s the Use?
My research uses these bijections in order to develop new ones between generalizations of plane partitions. A central result deals with plane partitions asymptotic to a Young diagram $\lambda$, which are analogous to skew semi-standard Young tableaux.
Ex: a plane partition asymptotic to $\lambda = (3, 2)$.
Thm: With $\operatorname{M}(q)$, $\operatorname{RPP}_\lambda(q)$, and $\operatorname{APP}_\lambda(q)$ denoting the generating functions for plane partitions, RPPs of shape $\lambda$, and plane partitions asymptotic to lambda, respectively,
$\displaystyle \operatorname{APP}_\lambda(q) = \operatorname{RPP}_\lambda(q)M(q)$.
This relation was formerly known only algebraically, but showing it bijectively was possible using $\operatorname{HG}$. A generalization of the relation was also bijectivized using Pak, and a bijectivizing a further generalization, which was shown algebraically by Jenne, Webb, and Young in 2020, remains an open problem.