%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2023}
\articlenumber{55}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{example}[thm]{Example}
\newtheorem{definition}[thm]{Definition}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{remark}[thm]{Remark}

\DeclareMathOperator{\col}{col}
\newcommand{\la}{\lambda}
\newcommand{\lam}{\lambda}
\newcommand{\lm}{\lambda/\mu}
\usepackage{youngtab}
\newcommand{\SSYT}{\mathrm{SSYT}}
\newcommand{\SYT}{\mathrm{SYT}}
\newcommand{\RPP}{\mathrm{RPP}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\Q}{\mathcal{Q}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Br}{\mathrm{Br}}
\newcommand{\z}{\mathbf{z}}
\newcommand{\NI}{\mathcal{NI}}
\newcommand{\nOOT}{\mathrm{OOT}}
\newcommand{\cOOT}{\mathcal{OOT}}
\newcommand{\NIP}{\mathcal{NIP}}
\newcommand{\dd}{\mathsf{d}}
\newcommand{\ED}{\mathcal{E}}
\newcommand{\nED}{\mathrm{ED}}
\newcommand{\HG}{HG}

\usepackage{subcaption}
\usepackage{ytableau}
\setitemize{noitemsep,topsep=0pt,parsep=0pt,partopsep=0pt}

%\usepackage{paralist}

%% define your title in the usual way
\title[Minimal skew SSYT and the Hillman--Grassl correspondence]{Minimal skew semistandard Young tableaux \\ and the Hillman--Grassl correspondence}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Alejandro H. Morales\thanks{\href{mailto:amoralesborr@umass.edu}{amoralesborr@umass.edu}. Morales is partially supported by NSF grant DMS-22030407.}\addressmark{1}, Greta Panova\thanks{\href{mailto:gpanova@usc.edu}{gpanova@usc.edu}. Panova is partially supported by NSF grant CCF-2007652.}\addressmark{2}, \and GaYee Park\thanks{\href{mailto:park.ga_yee@uqam.ca}{park.ga\_yee@uqam.ca}.}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, UMass, Amherst MA, USA \\ \addressmark{2}Department of Mathematics, University of Southern California, Los Angeles CA, USA \\ \addressmark{3}
LaCIM,  
Universit\'e du Qu\'ebec \`a Montr\'eal, Montr\'eal QC, Canada}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{Standard tableaux of skew shape are fundamental objects in enumerative and algebraic combinatorics and no product formula for the number is known. In 2014, Naruse gave a formula (NHLF) as a positive sum over excited diagrams of products of hook-lengths. Subsequently, Morales, Pak, and Panova gave several proofs and generalized it to two $q$-analogues. They also showed, partly algebraically, that the Hillman--Grassl map restricted to skew shapes must be a bijection. We study the problem of circumventing the algebraic part and proving the bijection completely combinatorially. For a skew shape, we define a new set of semi-standard Young tableaux, called the \emph{minimal SSYT}, that are equinumerous with excited diagrams via a new description of the Hillman--Grassl bijection and  a version of excited moves. Lastly, we relate the minimal skew SSYT with the terms of the Okounkov-Olshanski formula (OOF) for counting SYTs of skew shape. Our construction immediately implies that the summands in the NHLF are less than the summands in the OOF. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Standard Young tableaux, Hillman--Grassl correspondence}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblio_fpsac.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

\setlength\headheight{16pt}
Given a partition $\lambda \vdash n$, the number $f^{\lambda}$ of standard Young tableaux (SYT) of shape $\lambda$ is an important quantity in enumerative, algebraic, and probabilistic combinatorics and is given by the following \emph{hook-length formula} of Frame-Robinson-Thrall \cite{FRT} 1954.

\begin{thm}[Frame-Robinson-Thrall \cite{FRT}]
For $\lambda$ a partition of $n$ we have  
\begin{equation} \label{eq:hlf}
f^{\lambda} = \frac{n!}{\prod_{(i,j) \in [\lambda]} h(i,j)},
\end{equation}
where $[\lambda]$ is the Young diagram of $\lambda$ and $h(i,j)=\lambda_i-i+\lambda'_j-j+1$. 
\end{thm}



Unlike for straight shapes, there is no such product formula for the number $f^{\lambda/\mu}$ of SYT of skew shape $\lambda/\mu$. There is a determinantal
formula for $f^{\lambda/\mu}$ like the {\em Jacobi--Trudi identity}, which is efficient but inherently non-positive. There is a classical positive formula for $f^{\lambda/\mu}$ involving the {\em Littlewood--Richardson  coefficients} $c^{\lambda}_{\mu,\nu}$, which are themselves hard to compute.

Central to this paper are two other positive formulas for $f^{\lambda/\mu}$ coming from equivariant Schubert calculus or more explicitly from evaluations of {\em factorial Schur functions}: the Okounkov--Olshanski formula \cite{OO} from 1998 and the Naruse hook-length formula \cite{naruse2014} from 2014. We start with the latter since it resembles \eqref{eq:hlf}.


\begin{thm}[Naruse \cite{naruse2014}, \cite{MPP1}] \label{thm:IN}
For a skew shape $\lambda/\mu$ of size $n$ we have
\begin{equation} \label{eq:nhlf} \tag{NHLF}
f^{\lambda/\mu}  = n! \sum_{S \in \mathcal{E}(\lambda/\mu)}
 \prod_{u\in [\lambda]\backslash S} \frac{1}{h(u)},
\end{equation}
where $\mathcal{E}(\lambda/\mu)$ is
the set of {\em excited diagrams} of $\lambda/\mu$. 
\end{thm}

The excited diagrams of shape $\lambda/\mu$, denoted by $\mathcal{E}(\lambda/\mu)$, are certain subsets of size $|\mu|$ of the Young diagram of $\lambda$ obtained from the Young diagram of $[\mu]$ by recursively doing a local move $\beta$ \cite{IN}. Excited diagrams are in correspondence with certain SSYT of shape $\mu$ that are {\em flagged}, i.e. with certain bounds on the entries in each row. The Naruse formula has been actively studied \cite{CPP,,konvalinka1, MPP2,MPP1}.


The other positive formula by Okounkov-Olshanski is also a sum over certain SSYT of shape $\mu$ with entries at most $\ell(\lambda)$ called {\em Okounkov--Olshanski tableaux} $\cOOT(\lambda/\mu)$.

\begin{thm}[{Okounkov--Olshanskii \cite{OO}}]
For a skew shape $\lambda/\mu$ of size $n$ we have
\begin{equation} \label{eq:OO} \tag{OOF}
f^{\lambda/\mu} \, = \, \frac{n!}{\prod_{u\in [\lambda]} h(u)} \,
\sum_{T \in \cOOT(\lambda/\mu)} \, \prod_{(i,j)\in [\mu]} (\lambda_{\ell+1-T(i,j)} -i+j).
\end{equation}
\end{thm}

In \cite{MZ}, Morales--Zhu did a similar study of \eqref{eq:OO} as Morales--Pak--Panova did in \cite{MPP2,MPP1} for \eqref{eq:nhlf}. In particular, they gave in \cite[Cor. 5.7]{MZ} a reformulation of \eqref{eq:OO} in terms of the following flagged tableaux: SSYT of shape $\lambda/\mu$ with entries in row $i$ at most $i-1$, whose set we denote by $\mathcal{SF}(\lambda/\mu)$. 


\medskip

\noindent{\bf A new formulation of Naruse's formula:} A natural question, which is the start of our investigation, is to also find a reformulation of \eqref{eq:nhlf} in terms of some SSYT of skew shape $\lambda/\mu$. We define the set $\SSYT_{\min}(\lambda/\mu)$ of {\em minimal skew SSYT}  obtained from the \emph{minimum SSYT}, $T_0$ of shape $\lambda/\mu$ with entries $\{0,1,\ldots,\lambda'_i-\mu'_i-1\}$ by recursively doing local moves $\delta$. Our first result is a bijection $\Phi$ between excited diagrams and tableaux $\SSYT_{\min}(\lambda/\mu)$ that intertwines with the respective local moves $\beta$ and $\delta$, respectively. 




\begin{thm}\label{thm: bijection ED and SSYTmin}
For a skew shape $\lambda/\mu$ the map $\Phi:\E(\lambda/\mu) \to \SSYT_{\min}(\lambda/\mu)$ is a bijection that intertwines with the respective local moves, that is $\Phi \circ \beta = \delta \circ \Phi$.
\end{thm}


As a corollary, we obtain a new reformulation of \eqref{eq:nhlf}. Let $(\theta_1,\ldots,\theta_k)$ be the {\em Lascoux--Pragacz} decomposition of the shape $\lambda/\mu$ into border strips.




\begin{thm}[minimal SSYT version of \eqref{eq:nhlf}]
\label{cor: reformulation NHLF min tableaux}
For a skew shape $\lambda/\mu$ of size $n$ we have
\begin{equation} \label{eq:reformulate NHLF}
f^{\lambda/\mu} \,=\, \frac{n!}{\prod_{u \in [\lambda]} h(u)} \sum_{T \in \SSYT_{\min}(\lambda/\mu)} \prod_{(i,j)\in [\mu]} h(i+\alpha,j+\alpha),
\end{equation}
where $\alpha$ is the number strips $\theta_k$ such that $\overline{T}(\theta_k(j))>\mu'_j-i$ and $\overline{T}=T-T_0$.
\end{thm}


We give an explicit non-recursive description of the tableaux in $\SSYT_{\min}(\lambda/\mu)$  (\cref{thm: direct char min SSYT}) 
that immediately shows they are a subset of the skew flagged tableaux $\mathcal{SF}(\lambda/\mu)$ (see \cref{lemma: SSYT subset SF}). As a corollary, we obtain that the Okounkov--Olshanski formula has at least as many terms as the Naruse formula and characterize the skew shapes where equality is attained. We denote the number of terms of each formula by $\nED(\lambda)$ and $\nOOT(\lambda/\mu)$, respectively.

\begin{thm}
\label{thm: num ED vs OOF}
For a connected skew shape $\lambda/\mu$ with $d=\ell(\lambda)$ and $r=\max\{i\mid \mu_1=\mu_i\}$, we have that $\nED(\lambda/\mu) \leq \nOOT(\lambda/\mu)$ with equality if and only if  $\lambda_d\geq \mu_r+d-r$.
\end{thm}

\medskip
\noindent {\bf Relation with the Hillman--Grassl correspondence:} The hook-length formula \eqref{eq:hlf} has a $q$-analogue by Littlewood that is a special case of Stanley's hook-content formula for the generating series of SSYT of shape $\lambda$.

\begin{thm}[Littlewood]
For a partition $\lambda$ we have  
\begin{equation} \label{eq:qhlf}
s_{\lambda}(1,q,q^2,\ldots) \,=\, q^{\sum_i (i-1)\lambda_i}\cdot \prod_{u\in \lambda} \frac{1}{1-q^{h(u)}}.
\end{equation}
\end{thm}



This $q$-analogue has a bijective proof by Hillman--Grassl via the correspondence $HG(\cdot)$ between reverse plane partitions of shape $\lambda$ and arrays of nonnegative integers of shape $\lambda$. This correspondence is related to the famous RSK correspondence (see \cite{Gansner, MPP1}) and has recent connections to {\em quiver representations} \cite{GPT}.

In \cite{MPP1}, Morales--Pak--Panova gave a $q$-analogue of \eqref{eq:nhlf} for the generating functions of SSYT of skew shape $\lambda/\mu$. 

\begin{thm}[Morales--Pak--Panova~\cite{MPP1}] \label{thm:qNHLF skew}
For a skew shape $\lambda/\mu$ we have 
\begin{equation} \label{eq:qnhlf}
s_{\lambda/\mu}(1,q,q^2,\ldots) \,=\, \sum_{D \in \mathcal{E}(\lambda/\mu)} \prod_{(i,j)\in D} \frac{q^{\lambda'_j-i}}{1-q^{h(i,j)}}. 
\end{equation}
\end{thm}

Interestingly, this identity corresponds to restricting the Hillman--Grassl bijection to SSYT of shape $\lambda/\mu$ \cite{MPP1}. The resulting arrays $\mathcal{A}^*(\lm)$ have support on the complement of excited diagrams and with certain forced nonzero entries on {\em broken diagonals}. The proof of this connection with the Hillman--Grassl map $\HG(\cdot)$ is partly algebraic and remained mysterious. Our next results elucidate on this. 


First, we show that the bijection between minimal tableaux and excited diagrams coincides with the  Hillman--Grassl map.



\begin{thm}\label{PhivsHG}
The map $\Phi$ is equivalent to the inverse Hillman--Grassl map ${HG^{-1}}$ on the arrays $\mathcal{A}^*(\lambda/\mu)$. That is for $A_D$ in $\mathcal{A}^*(\lambda/\mu)$ we have
$HG^{-1}(A_D) \,=\, \Phi(D)$.
\end{thm}

As a corollary, we obtain a bijective proof of part of \eqref{eq:qnhlf} by taking the {\em leading terms} of each summand on the right-hand-side. 

\begin{cor}
 For a shape $\lambda/\mu$ we have 
$\sum_{T \in \SSYT_{\min}(\lambda/\mu)} q^{|T|} = \sum_{D \in
  \mathcal{E}(\lambda/\mu)}  q^{\sum_{(i,j)\in D} (\lambda'_j-i)}$.
\end{cor} 

We also give a fully bijective proof of \eqref{eq:qnhlf} for the case of {\em border strips}. The details of this last result and full version of this abstract will appear in \cite{MPPHG}. 



\section{Minimal semistandard tableaux of shape \texorpdfstring{$\lambda/\mu$}{}}

\subsection{Excited diagram and broken diagonals}


Given a subset $D$ of $[\lambda]$, a cell $(i,j)$ of $D$ is {\em active} if the cells $(i+1,j),(i,j+1),(i+1,j+1)$ are not in $D$ but are in $[\lambda]$. Given an active cell $(i,j)$ of $D$, let $\beta_{(i,j)}:D\to D'$ be the map that replaces cell $(i,j)$ in $D$ by $(i+1,j+1)$. We call such $\beta_{(i,j)}$ an \emph{excited move}.  An \emph{excited diagram} of $\lambda/\mu$ is a set of $|\mu|$ cells obtained from $[\mu] \subseteq [\lambda]$ by applying excited moves. We let $\mathcal{E}(\lambda/\mu)$ be the set of excited diagrams of $\lambda/\mu$ (see \cref{fig: beta move}). These diagrams were introduced by Ikeda--Naruse in \cite{IN}.

Each excited diagram $D$ is associated with the \emph{broken diagonals} $\Br(D)$, which are obtained from the sub-diagonals of $\lambda/\mu$ by applying excited moves. For $\beta_{(i,j)}:D\to D'$, then $\Br(D') = \Br(D) \setminus \{(i+1,j+1)\} \cup \{(i+1,j)\}$ (see \cref{fig: beta move}).





\begin{figure}[t]
     \begin{subfigure}[normal]{0.27\textwidth}
     \centering
     \includegraphics[height=2.1cm]{FPSACfigures/LascouxKreiman.pdf}
     \caption{}
     \label{fig: Lascoux Kreiman exmaple}
     \end{subfigure}
    \quad
     \begin{subfigure}[normal]{0.33\textwidth}
     \centering
    \includegraphics[height=2.1cm]{fpsacfigures/delta_example.pdf}
    \caption{}
    \label{fig: delta example}
    \end{subfigure}
    \quad
    \begin{subfigure}[normal]{0.33\textwidth}
    \centering
    \includegraphics[height=2.1cm]{fpsacfigures/Phi_example.pdf}
    \caption{}
    \label{fig: phi example}
    \end{subfigure}
    \caption{(a) Examples of the Lascoux--Pragacz decomposition and Kreiman decomposition of the skew shape $\lambda/\mu$. (b) Excited move $\delta$ on $\SSYT_{\min}$ (c) Excited diagram to $\SSYT_{\min}$}
    \label{fig: ssyt min}
\end{figure}

\subsection{Lascoux--Pragacz and Kreiman decomposition of \texorpdfstring{$\lambda/\mu$}{}}

We review two different decompositions of a Young diagram of shape $\lambda/\mu$ into \emph{strips} (connected skew shapes with no $2 \times 2$ box), see \cref{fig: Lascoux Kreiman exmaple} . 


The \emph{Lascoux-Pragacz decomposition} of $\lambda/\mu$ is a tuple of non-intersecting lattice paths $(\theta_1,\dots, \theta_k)$, where $\theta_1$ is the outer border strip of $\lambda$, which starts at the southwest corner of $[\lm]$ and ends at the northeast corner of $[\lm]$ \cite{LP}. Then $\theta_2$ is the outer border strip of $\lambda\setminus \theta_1$ and each $\theta_i$ is the outer border strip of $\lambda\setminus \theta_1\setminus \cdots \setminus \theta_{i-1}$. We assume each strip $\theta_i$ starts at the left or bottom of $[\lm]$ and ends at the right or top of $[\lm]$. Given a skew shape $\lambda/\mu$, and its Lascoux-Pragacz decompositions $(\theta_1,\dots,\theta_k)$, denote $\mathsf{f}(\theta_r)$ the row number of the top most element of $\theta_r$. We define the $\theta_r$-height of row $i$, denoted as $ht_{\theta_r}(i)$ to be $i - \mathsf{f}(\theta_r)$. For example, in \cref{fig: Lascoux Kreiman exmaple}, the height of the element $(7,2)$ in $\theta_1$ is $6$ whereas the height of $(4,1)$ in $\theta_4$ is $1$.


The \emph{Kreiman decomposition} of $\lambda/\mu$ is a tuple  $(\gamma_1,\dots,\gamma_k)$ of non-intersecting lattice paths  with support $[\lambda/\mu]$, where each $\gamma_i$ begins at the southwest corner and ends at northeast corner \cite{Kre1} (see \cref{fig: Lascoux Kreiman exmaple}). We denote $\epsilon_i$ the distance between $\gamma_1$ and $\gamma_i$.
The support of such paths are the complement of excited diagrams \cite[\S5, \S6]{Kre1}. If an excited diagram $D$ corresponds to the tuple $(\gamma'_1,\ldots,\gamma'_k)$, we denote by $\gamma_i(D)=\gamma'_i$, the path obtained from $\gamma_i$ after applying the corresponding {\em ladder moves} to the excited moves where $[\mu]$ is obtained from $D$ (see \cref{fig: beta move}). 



\begin{lem}\label{lemma: gamma-theta}
Let $(\gamma_1,\dots,\gamma_k)$ and $(\theta_1,\dots,\theta_k)$ be the Kreiman and Lascoux-Pragacz decomposition of shape $\lambda/\mu$. For each $i\in \{1,\dots,k\}$, let $\gamma_i:(f_i,g_i)\to(c_i,d_i)$ and $\theta_i:(s_i,t_i)\to (u_i,v_i)$. Then $g_i-t_i= \epsilon_i$, i.e. the column difference of the starting point of $\gamma_i$ and $\theta_i$ is $\epsilon_i$.
\end{lem}



\subsection{Minimal skew Semistandard Young Tableaux}

The minimal skew SSYT are obtained from the minimum SSYT $T_0$ by applying a sequence of \emph{excited moves} $\delta$, defined as follows (see \cref{fig: delta example}). 
Let $\lambda/\mu$ be a skew partition and $(\theta_1,\dots,\theta_k)$ be its Lascoux-Pragacz decomposition. Given a strip $\theta_k$ and column $j$, let $\theta_k(j)$ be the $j$th column segment of $\theta_k$. Let  $(i,j)$ be the top-most cell  and $(i',j)$ be the bottom-most cell of $\theta_k(j)$ (which may agree if the column has size one). 

\begin{definition}[excited move $\delta$] \label{def:delta move}
The column $\theta_k(j)$ of $T$ in $\SSYT(\lm)$ is  \emph{active} if 
\begin{itemize}
    \item[(i)] $T(i,j) < ht_{\theta_k}(i)$, 
    \item[(ii)] $T(i,j)< T(i, j+1)$ and $T(i',j)< T(i'+1,j)+1$.
\end{itemize}
Given an active column $\theta_k(j)$ of $T$, the \emph{excited move} $\delta$ adds one to each entry in the column segment $\theta_k(j)$ and $T':=\delta_{(k;j)}(T)$ be the tableau obtained from $T$ by the move $\delta$. 
\end{definition}


We define a bijection between $\E(\lambda/\mu)$ and $\SSYT_{\min}(\lambda/\mu)$ denoted $\Phi: \E(\lambda/\mu) \to \SSYT(\lambda/\mu)$, which commutes with the excited moves in $\E(\lambda/\mu)$ and  $\SSYT_{\min}(\lambda/\mu)$.

\begin{definition}\label{def: phi* bijection}
Given $D\in \E(\lambda/\mu)$, let $(\gamma_1(D),\ldots,\gamma_k(D))$ and $(\theta_1,\ldots, \theta_k)$ be its Kreiman and Lascoux-Pracgaz decomposition into paths and $\Br(D)$ be its set of broken diagonals. Let $b_j$ be the number of broken diagonals on the  $j$th column of $\gamma_i(D)$. For each $\gamma_i(D)$ and $\theta_i$, do the following procedure starting from the left most column of each path to obtain $T:=\Phi(D)$: 


\begin{itemize}
    \item[1.] Denote the bottom-most element of the $j$th column of $\theta_i$ as $(s_j,t_j)$. Let 
    \[
    T(s_j,t_j) = 
    \begin{cases}
    b_j & \text{ if } j=1,\\
    T(s_j,t_j-1) + b_j & \text{ if } j>1.
    \end{cases}
    \]
    \item[2.] Fill the rest of the $j$th column of $\theta_i$ so that each entry differs by $1$.
\end{itemize}
\end{definition}
The proof that $\Phi$ is well defined can be found in the full version \cite{MPPHG}.



\begin{example}
Let $D\in \E(\lambda/\mu)$ be the excited diagram shown in \cref{fig: phi example}. We apply the correspondence to obtain $T = \Phi(D)$. The first column of $\gamma_1(D)$ has three  broken diagonals, so $T(5,1) = 3$. the second column of $\gamma_1(D)$ has no broken diagonals , so $T(5,2)=3$, then the rest of the column of $\theta_1$ is filled with each entry differing by $1$ to maintain  column strictness. We continue the algorithm to obtain the final tableau $T$ of skew shape $\lm$.
\end{example}

For the Lascoux--Pragacz decomposition of $[\lm]$ and the Kreiman paths $(\gamma_1,\ldots,\gamma_k)$ corresponding to an excited diagram $D$, we denote by $\col_{\lm}(\theta_i,n)$ and $\col_{\lm}(\gamma_i,n)$ the column on $\lm$ where the $n$th column of $\theta_i$ and $\gamma_i$ is, respectively. 




\begin{lem}\label{lemma: beta and delta}
Given an excited diagram $D$ in $\mathcal{E}(\lambda/\mu)$ and an active cell $u=(a,b)$ of $D$ we have
\[
\Phi (\beta_u(D)) = \delta_{f(u)}(\Phi(D)),
\]
where $f(a,b)=(i;\mu(a,b))$, $i$ is the index of the Kreiman path $\gamma_i(D)$ modified by $\beta(a,b)$, and $\mu(a,b)$ is the column of the original cell in $\mu$ where $(a,b)$ came from.
\end{lem}


\begin{proof}
The excited move $\beta_{(a,b)}$ corresponds to a ladder move on $\gamma_i(D)\to \gamma_i(D')$, for some $i$ and a broken diagonal shift from $(a+1, b+1)$ to $(a+1,b)$. Let $g_i$ and $t_i$ be the starting column of $\gamma_i(D)$ and $\theta_i$, respectively. Suppose $(a+1,b)$ is in the $j$th column of the path $\gamma_i(D)$. Then the excited move $\beta_{(a,b)}$ shifts a broken diagonal to the $j$-th column of $\gamma_i(D')$, where $j = b-g_i+1$. The $j$-th column of $\gamma_i(D)$ corresponds to the $j$-th column of $\theta_i$, which corresponds  to  column $t_i+j-1$ of shape $\lambda/\mu$. By \cref{lemma: gamma-theta} we know that $g_i-t_i = \epsilon_i$. Thus we have that 
\[
\col_{\lm}(\theta_i, j) = t_i + j -1 = (g_i-\epsilon_i) + (b-g_i + 1) -1 = b- \epsilon_i.
\]
We know that $\epsilon_i$ is also the number of times $(a,b)$ has been excited, which is  $b-\mu(a,b)$. Therefore we have that $\col_{\lm}(\theta_i, j)=\mu(a,b)$. This shows that $\Phi(\beta_u(D))$ has increments of 1 on $\theta_i$ at column $\mu(a,b)$ compared to $\Phi(D))$. This is equivalent to what the move $\delta_{(i;\mu(a,b))}$ does on $\Phi(D)$. Thus $\Phi(\beta_u(D)) = \delta_{(i;\mu(a,b))}(\Phi(D))$, as desired.
\end{proof}

\begin{figure}
    \centering
    \begin{subfigure}[normal]{0.48\textwidth}
    \centering
    \includegraphics[width = 1\textwidth]{fpsacfigures/excited_example1.pdf}
    \caption{}
    \label{fig: beta move}
    \end{subfigure}
    \begin{subfigure}[normal]{0.48\textwidth}
    \centering
    \includegraphics[width = 1\textwidth]{fpsacfigures/excited_example2_fpsac.pdf}
    \caption{}
    \label{fig: delta move}
    \end{subfigure}
    \caption{(a) The $\E(55332/22)$, their corresponding $\gamma_i(D)$ (in \textcolor{blue}{blue}) and broken diagonals (in \textcolor{red}{red}). (b) The $\SSYT_{\min}(55332/22)$ with the active columns colored in yellow and red.}
    \label{fig:excited diagrams}
\end{figure}



\begin{proof}[Proof sketch of \cref{thm: bijection ED and SSYTmin}]
By \cref{lemma: beta and delta}, $\Phi$ intertwines the excited moves $\beta$ and $\delta$. One can check that  $\Phi$ is injective. Note that $\Phi([\mu])=T_0$. Given any excited diagram $D$ in $\ED(\lm)$, there exists a sequence $\beta_1,\ldots,\beta_m$ of excited moves such that $D=\beta_m \circ \cdots \circ \beta_1([\mu])$. Iterating \cref{lemma: beta and delta} gives that 
$
\Phi(D) = \delta_m \circ \cdots \circ \delta_1(T_0).$


Thus $\Phi(D)$ is in $\SSYT_{\min}(\lm)$ and so $\Phi(\ED(\lm))\subseteq \SSYT_{\min}(\lm)$. It remains to show that $\Phi(D)$ is surjective. Given $T$ in $\SSYT_{\min}(\lm)$, there exists a sequence of $\delta_1,\dots, \delta_k$ of excited moves such that $\delta_k \circ \cdots \circ \delta_1 (T_0) = T$. Again, iterating \cref{lemma: beta and delta} we have that for $D'=\beta_k \circ \cdots \circ \beta_1([\mu])$, one obtains $\Phi(D')=T$, as desired. 
\end{proof}

There is the following non-recursive description of the minimal SSYT. This new characterization will be related to the Okounkov--Olshanski tableaux in the next section. We omit the details of the proof.

\begin{thm} \label{thm: direct char min SSYT}
A SSYT $T$ of shape $\lm$ is in $\SSYT_{\min}(\lm)$ if and only if 
\begin{itemize}
    \item[(i)] For each $(i_r,j_r)$ in $\theta_r$, $T (i_r,j_r) \leq ht_{\theta_r}(i_r)$    \item[(ii)] For any $(i_r,j_r)$ and $(i_r+1,j_r)$ in $\theta_r$, $T (i_r+1,j_r) - T (i_r,j_r) = 1$.
\end{itemize}
\end{thm}

In other words, the set $\SSYT_{\min}(\lambda/\mu)$ consists of SSYT of shape $\lambda/\mu$ where the values along each path $\theta_r$ are bounded by the height $ht_{\theta_r}$ and the values along entries in the same column of a strip $\theta_r$ differ by one. 


\section{Reformulation of \texorpdfstring{\eqref{eq:nhlf}}{} and comparison with \texorpdfstring{\eqref{eq:OO}}{}} \label{sec: reformulation NHLF}



In this section we use the bijection $\Phi$ between minimal SSYT and excited diagrams of shape $\lm$ to reformulate the Naruse hook formula \eqref{eq:nhlf} in terms of minimal SSYT. We need the following description of the inverse of  $\Phi$.




\begin{lem}[Inverse of $\Phi$]\label{lemma: reformulation bijection}
Let $D\in \E(\lm)$ and recall $\overline{T} = T-T_0$, where $T_0$ is the minimum skew SSYT and $T = \Phi(D)$. Then 
\[D =  \{(i + \alpha, j+\alpha) \mid (i,j)\in [\mu]\},\]
where $\alpha$ is the number of strips $\theta_k$ such that $\overline{T}(\theta_k(j)) > \mu_j'-i$.
\end{lem}


\begin{proof}[Proof of \cref{cor: reformulation NHLF min tableaux}]
The result follows by combining the excited diagram formulation \eqref{eq:nhlf} of Naruse's formula and the description of inverse of $\Phi$ from \cref{lemma: reformulation bijection}.
\end{proof}



\begin{figure}
    \centering
    \begin{subfigure}[normal]{0.68\textwidth}
    \centering
    \includegraphics[scale=0.7]{fpsacfigures/reformulation_ED.pdf}
    \caption{}
     \label{fig: bijection min SSYT to excited diagrams}
    \end{subfigure}
    \begin{subfigure}[normal]{0.3\textwidth}
    \centering
    \includegraphics[scale=0.4]{fpsacfigures/ED=OOT_fpsac.pdf}
    \caption{}
     \label{fig:illustration equality terms}
    \end{subfigure}
    \caption{(a) Example of bijection $\Phi^{-1}$ between a minimal SSYT and excited diagrams for the shape $\lm=55552/21$. (b) Illustration of skew shapes $\lambda/\mu$ and their Lascoux--Pragacz decomposition with $\lambda_d\geq \mu_r+d-r$ where $\nED(\lambda/\mu)=\nOOT(\lambda/\mu)$.}
\end{figure}



\begin{example} \label{ex: inverse bijection for reformulation}
For the shape $\lm=55332/22$, from each of its minimal tableaux in \cref{fig: delta move} we find $\overline{T}$:
\[
\ytableausetup{smalltableaux}
\ytableaushort{\none\none000,\none\none000,000,000,00}* {5,5,3,3,2}
* [*(cyan)]{2,2,0,0,0},  \quad \ytableaushort{\none\none000,\none\none000,000,010,01}* {5,5,3,3,2}
* [*(cyan)]{2,2,0,0,0}, \quad \ytableaushort{\none\none000,\none\none000,000,010,11}* {5,5,3,3,2}
* [*(cyan)]{2,2,0,0,0}, \quad 
\ytableaushort{\none\none000,\none\none000,000,020,02}* {5,5,3,3,2}
* [*(cyan)]{2,2,0,0,0}, \quad 
\ytableaushort{\none\none000,\none\none000,000,020,12}* {5,5,3,3,2}
* [*(cyan)]{2,2,0,0,0}, \quad 
\ytableaushort{\none\none000,\none\none000,000,020,22}* {5,5,3,3,2}
* [*(cyan)]{2,2,0,0,0}
.  
\]
Next, for each $\overline{T}$ and $(i,j)$ in $\mu=[22]$, we find $\textcolor{red}{\alpha}$. Putting everything together using \eqref{eq:reformulate NHLF} gives
\begin{multline*}
f^{\lm} = \frac{14!}{9\, 8^2\, 7\, 6\,5^2\,4^2\,3^2\,2^4}{\big(}
h(1,1)h(1,2)h(2,1)h(2,2)+h(1,1)h(1,2)h(2,1)h(2{+}\textcolor{red}{1},2{+}\textcolor{red}{1})\\
+h(1,1)h(1{+}\textcolor{red}{1},2{+}\textcolor{red}{1})h(2,1)h(2{+}\textcolor{red}{1},2{+}\textcolor{red}{1})+h(1,1)h(1,2)h(2{+}\textcolor{red}{1},1{+}\textcolor{red}{1})h(2{+}\textcolor{red}{1},2{+}\textcolor{red}{1})+\\h(1,1)h(1{+}\textcolor{red}{1},2{+}\textcolor{red}{1})h(2{+}\textcolor{red}{1},1{+}\textcolor{red}{1})h(2{+}\textcolor{red}{1},2{+}\textcolor{red}{1})+h(1{+}\textcolor{red}{1},1{+}\textcolor{red}{1})h(1{+}\textcolor{red}{1},2{+}\textcolor{red}{1})h(2{+}\textcolor{red}{1},2{+}\textcolor{red}{1}){\big)}.
\end{multline*}
\end{example}


In the rest of this section we use the explicit non-recursive description of the skew minimal tableaux in $\SSYT_{\min}(\lambda/\mu)$ of \cref{thm: direct char min SSYT} to relate the number $\nED(\lm)$ of terms of \eqref{eq:nhlf} and the number $\nOOT(\lm)$ of terms of \eqref{eq:OO}. 


\begin{thm} \label{thm: ineq ED and OOF}
For a skew shape $\lambda/\mu$ we have that $\nED(\lambda/\mu) \leq \nOOT(\lambda/\mu)$.
\end{thm}

The proof follows immediately from the following lemma.

\begin{lem}\label{lemma: SSYT subset SF}
For a skew shape $\lm$ we have that $\SSYT_{\min}(\lambda/\mu) \subseteq \mathcal{SF}(\lambda/\mu)$.
\end{lem}


\begin{proof}
Let $T$ be a tableau in $\SSYT_{\min}(\lm)$. By Condition~(i) in \cref{thm: direct char min SSYT}, we have that for $(i,j)$ in $\theta_r$, $T(i,j) \leq ht_{\theta_r}(i)$. By definition of the height, we have that  $ht_{\theta_r}(i)\leq i-1$. Thus $T$ is a flagged tableau in $\mathcal{SF}(\lm)$. 
\end{proof}


\cref{thm: num ED vs OOF} characterizes the skew shapes where the Naruse hook-length formula and the Okounkov--Olshanski formula have the same number of terms.




\begin{proof}[Proof sketch of \cref{thm: num ED vs OOF}]
The inequality $\nED(\lm) \leq \nOOT(\lm)$ follows from \cref{thm: ineq ED and OOF}. By \cref{lemma: SSYT subset SF} we have that equality occurs if and only if all the flagged tableaux in $\mathcal{SF}(\lambda/\mu)$ are minimal. First, define the maximal tableau $T \in \mathcal{SF}(\lambda/\mu)$ as $T(i,j) =i-1$ for $(i,j) \in [\lambda/\mu]$, and let $(\theta_1,\ldots,\theta_k)$ be the Lascoux-Pragacz decomposition of $\lambda/\mu$. 

By the height condition in the definition of minimal tableaux (Condition~(i) in \cref{thm: direct char min SSYT}), it follows that all border strips $\theta_k$ reach the top row.  the border strips $\theta_k$ are entirely horizontal in the first $\mu_1$ columns of $\lambda/\mu$ and we have $d-r$ of them starting in the first $\mu_1$ columns. Thus $\lambda_d \geq \mu_1$. Also, since these border strips reach the top row, they must all cross the diagonal starting at $(r,\mu_r)$ and thus this diagonal extends to the last row of the shape, so $\lambda_d \geq \mu_r + d-r$, which proves the forward direction. See \cref{fig:illustration equality terms}.

For the other direction, if $\lambda_d \geq \mu_r+d-r$, then it is easy to see that all border strips  $\theta_i$ reach the top row and they are horizontal in the first $\mu_1$ columns. The tableaux in $\mathcal{SF}(\lambda/\mu)$ consisting of the columns past $\mu_1$ are of straight shape, and one can show the entries in row $i$ are $i-1$. For the first $\mu_1$ columns, since all border strips are horizontal, there are no further restrictions coming from the minimal tableaux. Thus $\SSYT_{\min}(\lambda/\mu)=\mathcal{SF}(\lambda/\mu)$, as desired.
\end{proof}

For shapes where $\nED(\lm)=\nOOT(\lm)$, this number is given by the hook-content formula. We omit the proof.

\begin{cor}
For a connected skew shape $\lambda/\mu$ satisfying $\lambda_d\geq \mu_r+d-r$ where $d=\ell(\lambda)$ and $r=\max\{i\mid \mu_1=\mu_i\}$, we have that \(\nED(\lm)=\nOOT(\lm) = s_{\mu}(1^{d-r})\).
\end{cor}







\section{The Hillman--Grassl correspondence and the map \texorpdfstring{$\Phi$}{}}

In this section, we sketch the proof of \cref{PhivsHG}. 

\subsection{Background on Hillman--Grassl}

We denote by $\HG(\cdot)$ the {\em Hillman--Grassl bijection} between reverse plane partitions in $\RPP(\lambda)$ ranked by size and integer arrays of shape $\lambda$ ranked by hook weight. That is, if $\HG:\pi \mapsto A$ then 
$|\pi|=\sum_{u \in \lambda} h(u)\cdot A_u$. We follow the definition of $\HG(\cdot)$ in \cite[\S7.22]{EC2}. This bijection also implies  \eqref{eq:qhlf} as a corollary.  

\begin{definition}[Hillman--Grassl correspondence]
The correspondence is obtained via a  sequence of pairs $(\pi_0,A_0):=(\pi,{\bf 0}),(\pi_1,A_1)\ldots,(\pi_k,A_k):=({\bf 0},\HG(\pi))$ where  each $\pi_i$ is a reverse plane partition and $A_i$ is an array of nonnegative integers of shape $\lambda$ obtained recursively as follows:
\begin{itemize}
    \item[(i)] start at the SW most nonzero cell of $\pi_i$, 
    \item[(ii)] traverse a  NE path: from cell $(a,b)$, if $(\pi_i)_{a,b}=(\pi_i)_{a-1,b}$ then the path moves North, otherwise the path moves East.
    \item[(iii)] Terminate when this is no longer possible. 
\end{itemize}
Let $u_i=(c,d)$ where $d$ is the column where the path starts and $c$ is the row where it ends.
Note that $|\pi_i|-|\pi_{i-1}|=h(u_i)$. We obtain the array $A_{i+1}$ from $A_i$ by adding one to cell $u_i$. 
We continue until $\pi_k$ as only zero entries. We let $A_k=\HG(\pi)$.  
\end{definition}



We extend $\HG$ to $\SSYT(\lambda/\mu)$ by viewing each skew SSYT $T$ as a plane partition of shape $\lambda$ with zero entries in $[\mu]$. 

For any excited diagram $D\in \E(\lambda/\mu)$, denote by $A_D$ the $0$-$1$ array of shape $\lambda$ with support on the broken diagonals $\Br(D)$ of $D$ and let $\mathcal{A}^*(\lm)=\{A_D \mid D\in \ED(\lm)\}$. Let $\mathcal{A}^*_D$ be the set of arrays $A$ of nonnegative integers of shape $\lambda$ with support contained in $[\lambda]\setminus D$ and positive entries $A_{i,j}>0$ if $(A_D)_{i,j}=1$. 

\begin{thm}[{\cite[Thm. 7.7]{MPP1}}] \label{thm: HG skew SSYT}
The (restricted) Hillman--Grassl map $\HG$ is a bijection
\[
\HG: \SSYT(\lm) \to \bigcup_{D\in \ED(\lm)} \mathcal{A}^*_D.
\]
\end{thm}

This property combined with the correspondence between RPPs and SSYTs of straight shape yields \eqref{eq:qnhlf} as a corollary (see \cite[Sec. 7.1]{MPP1}). The proof of this result is partly algebraic and the authors of \cite{MPP1} asked for a fully bijective proof. We make progress on this question by (i) giving a combinatorial proof for border strips $\lm$, and (ii) characterizing what is the image of $\SSYT_{\min}(\lm)$. We sketch the latter in the next section and the former is in \cite{MPPHG}.  

\subsection{Hillman--Grassl on minimal skew SSYT}

In this section we give the necessary lemmas to prove \cref{PhivsHG}. Fix a skew shape $\lm$ with Lascoux--Pragacz decomposition $(\theta_1,\ldots,\theta_k)$. 

Let $A_{\gamma_i(D)}$ be the a subarray of $A_D$ of shape $\lambda \setminus \cup_{j=1}^{i-1} \gamma_j(D)$ with support on the broken diagonal of $\gamma_i(D)$. We define the sum  $A_{\gamma_i(D)}+A_{\gamma_{i+1}(D)}$ as an array of shape $A_{\gamma_i(D)}$ with supports on the broken diagonals of $\gamma_i(D)$ and $\gamma_{i+1}(D)$. In other words, it is the entry-wise sum of the arrays where alignment of $A_{\gamma_i(D)}$ and $A_{\gamma_{i+1}(D)}$ corresponds to the original $A_D$ (see \cref{fig:HG theta}).

Similarly, let $T_{\theta_i}$ be a SSYT of shape $\lambda \setminus \cup_{j=1}^{i-1} \theta_j(D)$ with tableau entries  in $\theta_i$. We define the $T_{\theta_i} \cup T_{\theta_{i+1}}$ to be the tableaux of shape $T_{\theta_i}$ with entries of both $\theta_i$ and $\theta_{i+1}$.

The first lemma is a variation of \cref{PhivsHG} restricted to the individual $\gamma_i$ and $\theta_i$ (see \cref{fig:HG theta}).

\begin{lem}\label{lemma: theta gamma hg}
Let $D \in \ED(\lm)$ and $T=\Phi(D) \in \SSYT_{\min}(\lm)$. Then for $i=1,\ldots,k$ we have that \(HG(T_{\theta_i}) = A_{\gamma_i(D)}.\)

\end{lem}

\begin{figure}[h]
    \centering
     \begin{subfigure}[normal]{0.55\textwidth}
     \centering
     \includegraphics[width = 0.9 \textwidth]{fpsacfigures/HG_theta.pdf}
     \caption{}
     \label{fig:HG theta}
     \end{subfigure}
     \begin{subfigure}[normal]{0.44\textwidth}
     \centering
    \includegraphics[width = 1\textwidth]{fpsacfigures/HG_additive.pdf}
    \label{fig:hg additive}
    \caption{}
    \end{subfigure}
    \caption{(a) The Hillman--Grassl map of $T_{\theta_1}$, $T_{\theta_2}$, and $T_{\theta_3}$ separately (b) Additivity of the  Hillman--Grassl correspondence on $T_{\theta_i}$.}
    
\end{figure}





In order to show \cref{PhivsHG}, we need the following additivity results  (see \cref{fig:hg additive}). We define the sum of arrays $\HG(T_{\theta_i})$ and $\HG(T_{\theta_{i+1}})$ similarly to the sum of $A_{\gamma_i(D)}$ and $A_{\gamma_{i+1}(D)}$. We omit the technical proof by induction.




\begin{lem}\label{lem: union everything}
We have that  $\sum_{i=1}^k HG(T_{\theta_i}) = HG(T_{\theta_1\cup \dots \cup \theta_k}).$
\end{lem}




\begin{proof}[Proof sketch of \cref{PhivsHG}]
We have that $T_{\theta_1 \cup \cdots \cup \theta_k} = \Phi(D)$. We obtain the desired identity $\HG(\Phi(D)) = \sum_{i=1}^k A_{\gamma_i(D)} = A_D$ by \cref{lemma: theta gamma hg} and \cref{lem: union everything}.
\end{proof}



\acknowledgements{We thank Igor Pak, Hugh Thomas, and referees for helpful comments and suggestions.}


\printbibliography



\end{document}
