%% 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]{FPSAC2018}
\articlenumber{13}
%% 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}

\usepackage[utf8]{inputenc}
%usepackage{amsmath,amsthm,amssymb}
\usepackage{url}
%\usepackage[margin = 2.5cm]{geometry}
%\usepackage{stmaryrd}
\usepackage{tikz}
\usepackage{ytableau}
%\setlength{\parindent}{.5cm}



\newtheorem{theorem}{Theorem}[section]
\newtheorem*{main}{Theorem}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{conj}{Conjecture}
\newtheorem{question}{Question}
\theoremstyle{definition}
\newtheorem{alg}{Algorithm}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\rd}[1]{{\color{red} #1}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\tt arXiv:\nolinkurl{#1}}}

\def\cprime{$'$}
\newcommand{\ttt}{{\tilde{t}}}
\newcommand{\cat}{c}  %% Catalan numbers
\newcommand{\p}[1]{\mathcal #1}
\newcommand{\q}{q}   %% the numbers formerly called p_\lambda are now q_lambda
\newcommand{\s}{{\mathfrak S}}
\newcommand{\x}{{\bf x}}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\RST}{RST}
\newcommand{\Z}{{\mathbb Z}}

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

\usepackage{lipsum}

%% define your title in the usual way
\title{A bijective proof of the hook-length formula for skew shapes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Matja\v z Konvalinka\thanks{\href{mailto:matjaz.konvalinka@fmf.uni-lj.si}{matjaz.konvalinka@fmf.uni-lj.si}. The author acknowledges the financial support from the Slovenian Research Agency (research core funding No. P1-0294).}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Faculty of Mathematics and Physics, University of Ljubljana, and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia}

%% 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{Recently, Naruse presented a beautiful cancellation-free hook-length formula for skew shapes. The formula involves a sum over objects called \emph{excited diagrams}, and the term corresponding to each excited diagram has hook lengths in the denominator, like the classical hook-length formula due to Frame, Robinson and Thrall.\\
In this extended abstract, we present a simple bijection that proves an equivalent recursive version of Naruse's result, in the same way that the celebrated hook-walk proof due to Green, Nijenhuis and Wilf gives a bijective (or probabilistic) proof of the hook-length formula for ordinary shapes. In particular, we also give a new bijective proof of the classical hook-length formula, quite different from the known proofs.}

%% 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{hook-length formula, skew diagram, bijection}

%% 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, ie. [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{13-Konvalinka.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} \label{intro}

The celebrated \emph{hook-length formula} gives an elegant product expression for the number of standard Young tableaux (all definitions are given in Section \ref{def}):

$$f^\lambda = \frac{|\lambda|!}{\prod_{u \in [\lambda]} h(u)}$$

\smallskip

The formula also gives dimensions of irreducible representations of the symmetric group, and is a fundamental result in algebraic combinatorics.  The formula was discovered by Frame,
Robinson and Thrall in~\cite{FRT}. Since then, it has been reproved, generalized and extended in several different ways, and applied in a number of fields ranging from algebraic geometry to probability, and from group theory to the analysis of algorithms.

\smallskip

In an important development, Green, Nijenhuis and Wilf introduced the \emph{hook walk}, which proves a recursive version of the hook-length formula by a combination of a probabilistic and a short induction argument~\cite{GNW}. Zeilberger converted this hook-walk proof into a bijective proof~\cite{Zei}. With time, several variations of the hook walk have been discovered, most notably the $q$-version of Kerov~\cite{Ker1}. In \cite{ckp}, a weighted version of the identity is given, with a natural bijective proof in the spirit of the hook-walk proof. Also of note are the proofs of Franzblau and Zeilberger \cite{fz} and Novelli, Pak and Stoyanovskii \cite{nps}. See also \cite{sagan}, \cite{fischer}, \cite{kon} for some proofs of the hook-length formula for shifted tableaux. There are also a great number of proofs of the more general Stanley's hook-content formula (see e.g.~\cite[Corollary 7.21.4]{ec2}), see for example \cite{rw, krat2}.

%, and \cite{proctor} and the website \cite{proctorweb} for some information on $d$-complete posets, in which the hook-length formula also holds.

\smallskip

There is no (known) product formula for the number of standard Young
tableaux of a skew shape, even though some formulas have been known for a
long time. For example, \cite[Corollary 7.16.3]{ec2} gives a
determinantal formula; we can compute the numbers via Littlewood--Richardson coefficients with the formula $f^{\lambda/\mu} = \sum_\nu c_{\mu,\nu}^\lambda f^\nu$, and there is also a beautiful formula due to Okounkov and Olshanski \cite{oo}. The formula states that
\begin{equation}\label{oo}
f^{\lambda/\mu} = \frac{|\lambda/\mu|!}{\prod_{u \in [\lambda]} h(u)} \sum_{T \in \RST(\mu,\ell(\lambda))} \prod_{u \in [\mu]} (\lambda_{T(u)} - c(u)),
\end{equation}
where $\RST(\mu,\ell)$ is the set of \emph{reverse semistandard
tableaux}, tableaux with entries $1,\ldots,\ell$ with weakly decreasing
rows and strictly decreasing columns, and $c(u) = j -i$ is the
\emph{content} of the cell $u = (i,j)$. See also \cite[Section 10.3]{mpp}.

\smallskip

In 2014, Hiroshi Naruse \cite{naru} presented and outlined a proof of a
remarkable can\-cel\-la\-tion-free generalization for skew shapes,
somewhat similar in spirit to Okounkov--Olshanski's.

\smallskip

An \emph{excited move} means that we move a cell of a diagram diagonally (right and down), provided that the cells to the right, below and diagonally down-right are not in the diagram. Let $\p E(\lambda/\mu)$ denote the set of all \emph{excited diagrams} (see \cite{IN1}) of shape $\lambda/\mu$, diagrams in $[\lambda]$ obtained by taking the diagram of $\mu$ and performing series of excited moves in all possible ways. Naruse's formula says that

\begin{equation} \label{eq}
 f^{\lambda/\mu} = |\lambda/\mu|! \sum_{D \in \p E(\lambda/\mu)} \prod_{u \in [\lambda] \setminus D} \frac 1{h(u)}
\end{equation}
where all the hook lengths are evaluated in $[\lambda]$.

\smallskip

In \cite{mpp}, Morales, Pak and Panova give two different $q$-analogues
of Naruse's formula: for the skew Schur functions, and for counting
reverse plane partitions of skew shapes. The proofs of the former employ
a combination of algebraic and bijective arguments, using the factorial
Schur functions and the Hillman--Grassl correspondence. The proof of the
latter uses the Hillman--Grassl correspondence and is combinatorial. See also \cite{mpp2}.

\smallskip

The purpose of this extended abstract is to give a bijective proof of an
equivalent, recursive version of Naruse's result, in the same way that
the hook walk gives a bijective (or probabilistic) proof of the classical
hook-length formula. The bijection is quite easy to explain, and, in
particular, gives a new bijective proof of the classical hook-length
formula, rather different from the hook-walk proof or the proof due to
Novelli--Pak--Stoyanovskii.

\smallskip

Our main result (Theorem \ref{thm1}) is a polynomial identity, which specializes to the recursive version of equation \eqref{eq}. It was pointed out by Morales and Panova (personal communication) that the identity is equivalent to the identity \cite[equation (5.2)]{IN1}. See also Section \ref{final}.

\smallskip

In Section \ref{def}, we give basic definitions and notation. In Section
\ref{identity}, we motivate equation \eqref{eqmain} and show how it
implies \eqref{eq}. In Section \ref{bijection}, we use a version of the
bumping algorithm on tableaux to prove the identity bijectively. We
finish with some closing remarks in Section \ref{final}. The technical
proofs are presented in the full version of the paper (\cite[Section 5]{excited}).
\section{Basic definitions and notation} \label{def}

A \emph{partition} is a weakly decreasing finite sequence of positive integers $\lambda = (\lambda_1,\lambda_2,\ldots,\lambda_\ell)$. We call $|\lambda| = \lambda_1 + \cdots + \lambda_\ell $ the \emph{size} of $\lambda$ and $\ell = \ell(\lambda)$ the \emph{length} of $\lambda$. We write $\lambda_i = 0$ for $i > \ell(\lambda)$. The \emph{diagram} of $\lambda$ is $[\lambda] = \{(i,j) \colon 1 \leq i \leq \ell(\lambda), 1 \leq j \leq \lambda_i \}$. We call the elements of $[\lambda]$ the \emph{cells} of $\lambda$. For partitions $\mu$ and $\lambda$, we say that $\mu$ is \emph{contained} in $\lambda$, $\mu \subseteq \lambda$, if $[\mu] \subseteq [\lambda]$. We say that $\lambda/\mu$ is a \emph{skew shape} of size $|\lambda/\mu| = |\lambda| - |\mu|$, and the diagram of $\lambda/\mu$ is $[\lambda/\mu] = [\lambda] \setminus [\mu]$. We write $\mu \lessdot \lambda$ if $\mu \subseteq \lambda$ and $|\lambda/\mu| = 1$. In this case, we also say that $\lambda$ \emph{covers} $\mu$. We often omit parenthesis and commas, so we could write $\lambda = 6522$ instead of $\lambda = (6,5,2,2)$.

\smallskip

A \emph{corner} of $\lambda$ is a cell that can be removed from $[\lambda]$, i.e., a cell $(i,j) \in [\lambda]$ satisfying $(i+1,j),(i,j+1) \notin [\lambda]$. An \emph{outer corner} of $\lambda$ is a cell that can be added to $[\lambda]$, i.e., a cell $(i,j) \notin [\lambda]$ satisfying $i = 1$ or $(i-1,j) \in [\lambda]$ and $j = 1$ or $(i,j-1) \in [\lambda]$. The \emph{rank} of $\lambda$ is $r(\lambda) = \max\{ i \colon \lambda_i \geq i\}$. The square $[1,r(\lambda)] \times [1,r(\lambda)]$ is called the \emph{Durfee square} of $\lambda$. The partition $6522$ has corners $(1,6)$, $(2,5)$ and $(4,2)$, outer corners $(1,7)$, $(2,6)$, $(3,3)$ and $(5,1)$, and rank $2$.

\smallskip

The \emph{conjugate} of a partition $\lambda$ is the partition $\lambda'$ whose diagram is the transpose of $[\lambda]$; in other words, $\lambda'_j = \max \{ i \colon \lambda_i \geq j \}$. For example, for $\lambda = 6522$, we have $\lambda' = 442221$. The \emph{hook length} of the cell $(i,j) \in [\lambda]$ is defined by $h(i,j) = \lambda_i + \lambda'_j - i - j + 1$. For example, the hook length of the cell $(1,2) \in [6522]$ is $8$. The \emph{hook} of a cell $u = (i,j) \in [\lambda]$ is $H(u) = \{(i,j') \colon j \leq j' \leq \lambda_i \} \cup \{(i',j) \colon i \leq i' \leq \lambda'_j\}$. Obviously, we have $|H(u)| = h(u)$. The diagram $[\lambda]$ is the disjoint union of $H(i,i)$, $1 \leq i \leq r(\lambda)$.

\smallskip

A \emph{standard Young tableau} (or \emph{SYT}) of shape $\lambda$ is a bijective map $T \colon [\lambda] \to \{1,\ldots,|\lambda|\}$, $(i,j) \mapsto T_{ij}$, satisfying $T_{ij} < T_{i,j+1}$ if $(i,j),(i,j+1) \in [\lambda]$ and $T_{ij} < T_{i+1,j}$ if $(i,j),(i+1,j) \in [\lambda]$. The number of SYT's of shape $\lambda$ is denoted by $f^\lambda$. The following illustrates $f^{32} = 5$:

\smallskip

{ \begin{center}
\ytableausetup{centertableaux}
\ytableausetup{smalltableaux}
\begin{ytableau}
1 & 2 & 3 \\
4 & 5
\end{ytableau}
\qquad
\begin{ytableau}
1 & 2 & 4 \\
3 & 5
\end{ytableau}
\qquad
\begin{ytableau}
1 & 2 & 5 \\
3 & 4
\end{ytableau}
\qquad
\begin{ytableau}
1 & 3 & 4 \\
2 & 5
\end{ytableau}
\qquad
\begin{ytableau}
1 & 3 & 5 \\
2 & 4
\end{ytableau}
\end{center}}

\smallskip

The \emph{hook-length formula} gives a product expression for the number of standard Young tableaux: $f^\lambda = \frac{|\lambda|!}{\prod_{u \in [\lambda]} h(u)}$. For example, $f^{32} = \frac{5!}{4 \cdot 3 \cdot 1 \cdot 2 \cdot 1} = 5$.

\smallskip

Analogously, if $\mu \subseteq \lambda$, we can define a standard Young tableau of skew shape $\lambda/\mu$ as a map $T \colon [\lambda/\mu] \to \{1,\ldots,|\lambda/\mu|\}$, $(i,j) \mapsto T_{ij}$, satisfying $T_{ij} < T_{i,j+1}$ if $(i,j),(i,j+1) \in [\lambda/\mu]$ and $T_{ij} < T_{i+1,j}$ if $(i,j),(i+1,j) \in [\lambda/\mu]$. The number of SYT's of shape $\lambda/\mu$ is denoted by $f^{\lambda/\mu}$. The following illustrates $f^{43/2} = 9$:

\begin{center}
\ytableausetup{centertableaux}
\ytableausetup{smalltableaux}
\begin{ytableau}
\none & \none & 1 & 2 \\
3 & 4 & 5
\end{ytableau} \,
\begin{ytableau}
\none & \none & 1 & 3 \\
2 & 4 & 5
\end{ytableau} \,
\begin{ytableau}
\none & \none & 1 & 4 \\
2 & 3 & 5
\end{ytableau} \,
\begin{ytableau}
\none & \none & 1 & 5 \\
2 & 3 & 4
\end{ytableau} \,
\begin{ytableau}
\none & \none & 2 & 3 \\
1 & 4 & 5
\end{ytableau} \,
\begin{ytableau}
\none & \none & 2 & 4 \\
1 & 3 & 5
\end{ytableau} \,
\begin{ytableau}
\none & \none & 2 & 5 \\
1 & 3 & 4
\end{ytableau} \,
\begin{ytableau}
\none & \none & 3 & 4 \\
1 & 2 & 5
\end{ytableau} \,
\begin{ytableau}
\none & \none & 3 & 5 \\
1 & 2 & 4
\end{ytableau}
\end{center}

\smallskip

Suppose that $D \subseteq [\lambda]$. If $(i,j) \in D$, $(i+1,j),(i,j+1),(i+1,j+1) \in [\lambda] \setminus D$, then an \emph{excited move} with respect to $\lambda$ is the replacement of $D$ with $D' = D \setminus \{(i,j)\} \cup \{(i+1,j+1)\}$. If $\mu \subseteq \lambda$, then an \emph{excited diagram} of shape $\lambda/\mu$ is a diagram contained in $[\lambda]$ that can be obtained from $[\mu]$ with a series of excited moves. Let $\p E(\lambda/\mu)$ denote the set of all excited diagrams of shape $\lambda/\mu$. The following shows $\p E(43/2)$:

\smallskip

\begin{center} \label{e432}
\ytableausetup{smalltableaux}
 \begin{ytableau}
 *(gray) & *(gray) & & \\
  & &\\
\end{ytableau}
\qquad
\ytableausetup{smalltableaux}
 \begin{ytableau}
 *(gray) & & & \\
  & & *(gray) \\
\end{ytableau}
\qquad
\ytableausetup{smalltableaux}
 \begin{ytableau}
 {} &  & & \\
  & *(gray)&*(gray)\\
\end{ytableau}
\end{center}

\smallskip

As stated in the Introduction, Naruse's formula \eqref{eq} says that

\begin{equation*}
 f^{\lambda/\mu} = |\lambda/\mu|! \sum_{D \in \p E(\lambda/\mu)} \prod_{u \in [\lambda] \setminus D} \frac 1{h(u)},
\end{equation*}
where all the hook lengths are evaluated in $[\lambda]$. For example, the formula confirms that $f^{43/2} = 5! \left( \frac 1{3 \cdot 1 \cdot 3 \cdot 2 \cdot 1} + \frac 1{4 \cdot 3 \cdot 1 \cdot 3 \cdot 2} + \frac 1{5 \cdot 4 \cdot 3 \cdot 1 \cdot 3} \right) = 9$.

\section{A polynomial identity} \label{identity}

It is clear that both sides of \eqref{eq} are equal to $1$ if $\lambda = \mu$. Since the minimal entry of a standard Young tableau of shape $\lambda/\mu$ must be in an outer corner of $\mu$ which lies in $\lambda$, we have $f^{\lambda/\mu} = \sum_{\mu \lessdot \nu \subseteq \lambda} f^{\lambda/\nu}$, where $\sum_{\mu \lessdot \nu \subseteq \lambda}$ denotes the sum over all partitions $\nu$ that are contained in $\lambda$ and cover $\mu$. To prove equation \eqref{eq}, it is enough to show that its right-hand satisfies the same recursion. After multiplying with $\prod_{u \in [\lambda]} h(u)$, we see that the statement is equivalent to the following identity:

\begin{equation} \label{eq2}
(|\lambda| - |\mu|) \sum_{D \in \p E(\lambda/\mu)} \prod_{u \in D} h(u) = \sum_{\mu \lessdot \nu \subseteq \lambda} \sum_{D \in \p E(\lambda/\nu)} \prod_{u \in D} h(u).
\end{equation}

\begin{example}
 Take $\mu = 2$ and $\lambda = 43$. The three excited diagrams on page \pageref{e432} show that the left-hand side of \eqref{eq2} equals $(7 - 2) \left( 5 \cdot 4 + 5 \cdot 1 + 2 \cdot 1 \right) = 135$. On the other hand, there are two partitions $\nu$ that cover $\mu$, and together they give three excited diagrams:

 \smallskip

 \begin{center}
  \ytableausetup{smalltableaux}
 \ytableausetup{aligntableaux=top}
 \ytableaushort  {\none}  * {4,3}  * [*(gray)]{3}
\qquad\qquad
 \ytableaushort  {\none}  * {4,3}  * [*(gray)]{2,1}
  \qquad\qquad
 \begin{ytableau}
 *(gray) &  &  &   \\
 *(gray)&  & *(gray)
\end{ytableau}
\end{center}

 \smallskip

 That means that the right-hand side of \eqref{eq2} equals $5 \cdot 4 \cdot 3 + 5 \cdot 4 \cdot 3 + 5 \cdot 3 \cdot 1 = 135$.
\end{example}

For $i,j = 1,2,\ldots$, define
\begin{equation} \label{xy}
x_i = \lambda_i - i + \frac 1 2, \qquad y_j = \lambda'_j - j+ \frac 1 2.
\end{equation}

Clearly, for a cell $u = (i,j) \in [\lambda]$, we have $h(u) = \lambda_i + \lambda'_j - i - j + 1 = x_i + y_j$. Furthermore, since $[\lambda]$ is the disjoint union of hooks $H(i,i)$, $1 \leq i \leq r(\lambda)$, we have
\begin{equation} \label{size}
 |\lambda| = x_1 + y_1 + \cdots + x_{r(\lambda)} + y_{r(\lambda)}.
\end{equation}

For $\lambda = 43$, we have  $x_1 = 3 \frac 1 2$, $y_1 = 1 \frac 1 2$, $x_2 = 1 \frac 1 2$, $y_2 = \frac 1 2$, and indeed $|\lambda| = x_1 + y_1 + x_2 + y_2 = 7$. Equation \eqref{eq2} is therefore equivalent to the following:

\begin{equation} \label{eq3}
\left( \sum_{i=1}^{r(\lambda)} (x_i + y_i) - |\mu| \right) \sum_{D \in \p E(\lambda/\mu)} \prod_{(i,j) \in D} (x_i + y_j) = \sum_{\mu \lessdot \nu \subseteq \lambda} \sum_{D \in \p E(\lambda/\nu)} \prod_{(i,j) \in D} (x_i + y_j)
\end{equation}

Note that this is \emph{not} a valid polynomial identity for every $\lambda$, $\mu$: the right-hand side is a homogeneous polynomial (of degree $|\mu|+1$), while the left-hand side is not (except if $\mu = \emptyset$ or $\mu \not\subseteq \lambda$). It represents a valid identity only for specific values of $x_i$'s and $y_i$'s.

\smallskip

However, we can replace $|\lambda| - |\mu|$ on the left-hand side of equation \eqref{eq2} with a certain \emph{homogeneous} linear polynomial (and $h(u)$ again by $x_i + y_j$ if $u = (i,j)$) and get a valid polynomial identity. This identity specializes to \eqref{eq2} for appropriate values of $x_i$'s and $y_i$'s. The motivation for the result is the following lemma, which holds even if $\mu \not\subseteq \lambda$.

\begin{lemma} \label{w}
 For arbitrary partitions $\lambda,\mu$ and $x_k = \lambda_k - k + \frac 1 2$, $y_k = \lambda'_k - k + \frac 1 2$, we have
 $$|\lambda| - |\mu| = \sum_{\substack{\nexists i \colon \lambda_k - k \\= \mu_i - i}} x_k + \sum_{\substack{\nexists j \colon \lambda'_k - k \\= \mu'_j - j}} y_k$$
\end{lemma}

Note that while $k$, $i$ and $j$ appearing in the sums can be arbitrarily large, the summation is finite since $\lambda_k - k = \mu_k -k = -k$ and $\lambda'_k -k = \mu'_k -k = -k$ for large $k$.

\begin{example}
 We continue with the previous example, i.e., take $\mu = 2$ and $\lambda = 43$. We have
$$ \begin{array}{rlrl}
 (\lambda_k-k)_{k \geq 1} =& (\underline{3},1,-3,-4,-5,\ldots) & (\mu_i-i)_{i \geq 1} = & (1,-2,-3,-4,\ldots) \\
 (\lambda'_k-k)_{k \geq 1} =& (\underline 1,0,-1,-3,-5,-6,-7,\ldots) & (\mu'_j-j)_{j \geq 1} = & (0,-1,-3,-4,-5,\ldots)
\end{array}$$
 where elements of $(\lambda_k-k)_{k \geq 1}$ and $(\lambda'_k-k)_{k \geq 1}$ are underlined if they do not appear in $(\mu_i-i)_{i \geq 1}$ and $(\mu'_j-j)_{j \geq 1}$. Indeed, $|\lambda| - |\mu| = x_1 + y_1 = 5$. For $\mu = 431$ and $\lambda = 765521$,
$$ \begin{array}{rlrl}
 (\lambda_k-k)_{k \geq 1} =& (\underline 6,\underline 4,\underline 2,1,\underline{-3},-5,-7,-8,\ldots) & (\mu_i-i)_{i \geq 1} = & (3,1,-2,-4,-5,\ldots) \\
(\lambda'_k-k)_{k \geq 1} =& (\underline 5,\underline 3,\underline 1,0,-1,\underline{-4},-6,-8,-9,\ldots) & (\mu'_j-j)_{j \geq 1} = & (2,0,-1,-3,-5,-6,\ldots)
\end{array}$$
 and $|\lambda| - |\mu| = x_1 + x_2 + x_3 + x_5 + y_1 + y_2 + y_3 + y_6 = 18$.
\end{example}

The following theorem is our main result. It is a subtraction-free polynomial identity, which, by Lemma \ref{w}, specializes to equation \eqref{eq2} when $x_i = \lambda_i - i + \frac 1 2$ and $y_j = \lambda'_j - j + \frac 1 2$, and therefore implies the hook-length formula for skew diagrams.

\begin{theorem} \label{thm1}
For arbitrary partitions $\lambda$, $\mu$ and commutative variables $x_i,y_j$, we have
\begin{equation} \label{eqmain}
\Bigg( \sum_{\substack{\nexists i \colon \lambda_k - k \\= \mu_i - i}} x_k + \sum_{\substack{\nexists j \colon \lambda'_k - k \\= \mu'_j - j}} y_k \Bigg) \sum_{D \in \p E(\lambda/\mu)} \prod_{(i,j) \in D} (x_i + y_j) = \sum_{\mu \lessdot \nu \subseteq \lambda} \sum_{D \in \p E(\lambda/\nu)} \prod_{(i,j) \in D} (x_i + y_j).
\end{equation}
\end{theorem}

\begin{example}
 For $\mu = 2$ and $\lambda = 43$, we have the following identity (valid for commutative variables $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$).
 \begin{multline*}
 (x_1+y_1) \left( (x_1+y_1)(x_1+y_2) + (x_1+y_1)(x_2+y_3) + (x_2+y_2)(x_2+y_3) \right) \\
  = (x_1+y_1)(x_1+y_2)(x_1+y_3) + (x_1+y_1)(x_1+y_2)(x_2+y_1) + (x_1+y_1)(x_2+y_3)(x_2+y_1).
 \end{multline*}
 For $\mu = 431$ and $\lambda = 765521$, the first term on the left is $x_1 + x_2 + x_3 + x_5 + y_1 + y_2 + y_3 + y_6$, the second term is a sum of $14080$ monomials, and the right-hand side is a sum of $112640$ monomials.
\end{example}

The (bijective) proof of Theorem \ref{thm1} is the content of the next section.

\section{The bijection} \label{bijection}

First, we interpret the two sides of equation \eqref{eqmain} in terms of certain tableaux. To motivate the definition, look at the following excited diagram for $\mu = 431$ and $\lambda = 765521$:

\smallskip

\begin{center}
   \ytableausetup{smalltableaux}
 \ytableausetup{aligntableaux=top}
 \begin{ytableau}
 *(gray) & *(gray) &  &  &  &  & \\
 *(gray)&  &  & *(gray) & *(gray) &\\
 & & *(gray) & & \\
 & *(gray) & & & *(gray) \\
 & \\
 \\
 \end{ytableau}
\end{center}

\smallskip

Instead of actually moving the cells of $\mu$, write an integer in a cell of $\mu$ that indicates how many times it moves (diagonally) from the original position. For the above example, we get the following tableau of shape $\mu = 431$:

\smallskip

\begin{center}
   \ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=top}
 \ytableaushort
{0011,012,1}
\end{center}

\smallskip

It is easy to see that the (non-negative integer) entries of the
resulting tableau are weakly increasing along rows and columns (in other
words, that the tableau is a \emph{reverse plane partition}): for
example, if one cell is to the left of another, we cannot make an excited
move on it until we make an excited move on its right neighbor. Also,
every tableau with non-negative integer entries and weakly increasing
rows and columns corresponds to a valid excited diagram, provided that
the entry $r$ in row $i$ and column $j$ satisfies $j + r \leq
\lambda_{i+r}$. Furthermore, it is enough to check this inequality only
for the corners of $\mu$. See also \emph{flagged tableaux} in
\cite[Section 3.2]{mpp}.

\smallskip

The contribution  $\prod_{(i,j) \in D} (x_i + y_j)$ of an excited diagram $D$ can be written as
$$\prod_{(i,j) \in [\mu]} (x_{i+T_{ij}} + y_{j+T_{ij}}),$$
where $T$ is the corresponding tableau of shape $\mu$ with non-negative integer entries and weakly increasing rows and columns. To extract the monomials from the product, choose either $x_{i+T_{ij}}$ or $y_{j+T_{ij}}$ for each $(i,j) \in [\mu]$. Write the number $T_{ij}$ in position $(i,j)$ in black if we choose $x_{i+T_{ij}}$, and in red if we choose $y_{j+T_{ij}}$. Call a tableau with non-negative integer black or red entries and weakly increasing rows and columns a \emph{bicolored tableau}. Denote by $\p B(\mu)$ the (infinite unless $\mu = \emptyset$) set of bicolored tableaux of shape $\mu$, and denote by $\p B(\mu,\lambda)$ the (finite) set of bicolored tableaux $T$ of shape $\mu$ that satisfy $j + T_{ij} \leq \lambda_{i+T_{ij}}$ for all $(i,j) \in [\mu]$. The weight of a bicolored tableau $T$ of shape $\mu$ is
$$w(T) = \prod_{(i,j) \in b(T)} x_{i + T_{ij}} \prod_{(i,j) \in [T] \setminus b(T)} y_{j + T_{ij}}$$
where $b(T)$ is the set of black entries of $T$.

\begin{example}
 The following are some bicolored tableaux in $\p B(431)$. A bicolored tableau is in $\p B(431,765521)$ if and only if $T_{14} \leq 1$, $T_{23} \leq 2$, $T_{31} \leq 1$, so the first three are in $\p B(431,765521)$ and the last one is not.

 \smallskip

 \begin{center}
   \ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=top}
 \ytableaushort
{0{\rd 0}00,01{\rd 1},0}
\qquad \qquad \ytableaushort
{{\rd 0}0 {\rd 1}1,0{\rd 2}2,{\rd 1}}
\qquad \qquad \ytableaushort
{{\rd 1}{\rd 1}{\rd 1}1,{\rd 1}{\rd 2}2,1}
\qquad \qquad \ytableaushort
{01{\rd 1}1,2{\rd 2}2,{\rd 2}}
\end{center}

\smallskip

\noindent
The weights of these tableaux are $x_1^3x_2y_2x_3^2y_4$, $x_1y_1x_2^2y_2x_4y_4^2$, $x_2y_2^2y_3x_4^2y_4^2$, and $x_1x_2^2y_3x_4^2y_4^2$-
\end{example}

\smallskip

We are ready to interpret both sides of equation \eqref{eqmain}. The left-hand side is the enumerator (with respect to weight $w$) of the Cartesian product $\p B(\mu,\lambda) \times \p W(\mu,\lambda)$, where
$$\p W(\mu,\lambda) = \{x_k \colon \lambda_k - k \neq \mu_i - i \mbox{ for all } i\} \cup \{y_k \colon \lambda'_k - k \neq \mu'_j - j \mbox{ for all } j\}.$$
The right-hand side is the enumerator of the set $\bigcup_{\nu} \p B(\nu,\lambda)$, where the union is over all partitions $\nu$ that cover $\mu$ and are contained in $\lambda$.
%$\p W(\mu,\lambda)$ is the set of variables that appear in $\sum_{i=1}^{r(\lambda)} (x_i + y_i) - \sum_{i = 1}^{r(\mu)} (s_i + t_i)$.

\smallskip

In the remainder of this section, we present a weight-preserving bijection between the two sides. The map is a natural bumping algorithm. To describe it, we first describe the \emph{insertion process}: the process of inserting a variable $z \in \{x_1,y_1,x_2,y_2,\ldots \}$ into a bicolored tableau $T$ of shape $\mu$.

\smallskip

After some number of steps, $i$, $j$, $w$ and $S$ have certain values; in the beginning, $i = j = 0$, $w = z$ and $S = T$. If $w = x_k$, increase $j$ by $1$ (i.e., move to the next column) and find the largest possible $i$ (which can also be $\mu_j' + 1$ if $j = 1$ or $\mu'_j < \mu'_{j-1}$) so that we can replace $S_{ij}$ by a black $k - i$ in position $(i,j)$ and still have a weakly increasing column with non-negative integers (such an $i$ always exists). If, on the other hand, $w = y_k$, increase $i$ by $1$ (i.e., move to the next row) and find the largest possible $j$ (which can also be $\mu_i + 1$ if $i = 1$ or $\mu_i < \mu_{i-1}$) so that we can replace $S_{ij}$ by a red $k - j$ in position $(i,j)$ and still have a weakly increasing row with non-negative integers.

\smallskip

Let $w$ denote the value of the old $S_{ij}$ (i.e., $x_{i+S_{ij}}$ if $S_{ij}$ is black and $y_{j+S_{ij}}$ if $S_{ij}$ is red). Continue with the procedure until $(i,j)$ is an outer corner of $\mu$, and $S$ is a bicolored tableau of some shape $\nu$ which covers $\mu$. The procedure returns this final $S$, which we denote $\psi_\mu(T,z)$.

\begin{example} \label{ex}
 Take $\mu = 431$, the bicolored tableau
% \begin{center}
$$T =     \ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{0{\rd 0}{\rd 0}1,01{\rd 1},0}$$
% \end{center}
 and $z = y_1$. Since we are inserting a $y$-variable, we insert it into the first row. The variable $y_1$ can only be represented by a red $0$ in the first column, so we write a red $0$ in position $(1,1)$, and the variable bumped out is $x_1$ (represented by the black $0$ that was in position $(1,1)$ originally). Since this is an $x$-variable, we move to the right, and insert it into the second column. The variable $x_1$ can only be represented by a black $0$ in the first row, so we write a black $0$ in position $(1,2)$, and the variable bumped out is $y_2$ (represented by the red $0$ that was in position $(1,2)$ before). We have to insert it into the second row, either as a red $1$ in position $(2,1)$ or a red $0$ in position $(2,2)$. Of course, a red $1$ in position $(2,1)$ would give a decrease in column $1$, so we insert it in position $(2,2)$, and bump out a black $1$, representing $x_3$. We insert $x_3$ in column $3$, either as a black $2$ in row $1$ (but which makes the entry in $(3,1)$ larger than the entry in $(3,2)$) or as a black $1$ in row $2$. Thus we write a black $1$ in position $(3,2)$ and bump out the red $1$ representing $y_4$. We move to the next row: we can either write a red $3$ in position $(3,1)$ or a red $2$ in position $(3,2)$. Both are possible, so we pick the latter option. Now $(i,j) = (3,2)$ is an outer corner of $\mu$, so we terminate the insertion process. Figure \ref{path} illustrates the insertion process. Two numbers in a cell mean that we the number on the left is bumping the number on the right. The last tableau is $\psi_{431}(T,y_1)$.
\end{example}

\begin{figure}[h]
\ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{{\rd 0}0}{\rd 0}{\rd 0}1,01{\rd 1},0} \qquad
\ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{\rd 0}{0 \rd 0}{\rd 0}1,01{\rd 1},0} \qquad
\ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{\rd 0}0{\rd 0}1,0{{\rd 0}1}{\rd 1},0} \qquad
\ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{\rd 0}0{\rd 0}1,0{\rd 0}{1 \rd 1},0}\qquad
\ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{\rd 0}0{\rd 0}1,0{\rd 0}1,0{\rd 2}}
\caption{The insertion process from Example \ref{ex}.} \label{path}
\end{figure}


\begin{theorem} \label{insert}
 The insertion process described above always terminates and is a weight-preserving bijection
 $$\psi_\mu \colon \p B(\mu) \times \{x_1,y_1,x_2,y_2,\ldots \} \longrightarrow \bigcup_{\nu} \p B(\nu),$$
 where the union is over all partitions $\nu$ which cover $\mu$.
\end{theorem}

\smallskip

Of course, the bijection does not necessarily restrict to a bijection from $\p L(\mu,\lambda) = \p B(\mu,\lambda) \times \p W(\mu,\lambda)$ to $\p R(\mu,\lambda) = \bigcup_{\nu} \p B(\nu,\lambda)$, and does not immediately prove Theorem \ref{thm1}. Once we insert a variable from $\p W(\mu,\lambda)$ into a bicolored tableau in $\p B(\mu,\lambda)$, the resulting tableau can add an outer corner of $\mu$ which is not in $[\lambda]$, or it can return a bicolored tableau in $\p B(\nu)$, $\nu \subseteq \lambda$, which is not in $\p B(\nu, \lambda)$. For instance, the last example produced a tableau in $\p B(432) \setminus \p B(432,765521)$.

\smallskip

If $\psi_\mu(T,z) \in \p B(\nu)$ is not in $\p R(\mu,\lambda)$, we can remove the entry in the unique cell in $[\nu/\mu]$ and obtain a new variable $z'$ and a tableau $T'$ of shape $\mu$. Compute  $\psi_\mu(T',z') \in \p B({\nu}')$. If it is in $\p R(\mu,\lambda)$, terminate the procedure, otherwise remove the entry in the unique cell in $[{\nu}'/\mu]$ and obtain a new variable $z''$ and a tableau $T''$ of shape $\mu$. Continue until the computed tableau is in $\p R(\mu,\lambda)$; the procedure returns this tableau as the result. We call this the \emph{repeated insertion process}.

\begin{example}
 Take $\mu = 431$, $\lambda = 765521$,
 $$T =     \ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{0{\rd 0}{\rd 0}1,01{\rd 1},0}
\in \p B(431,765521)$$
 and $z = y_1 \in \p W(431,765521)$. We already computed
 $$\psi_{431}(T,z) = \ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{\rd 0}0{\rd 0}1,0{\rd 0}1,0 {\rd 2}} \in \p B(432) \setminus \p B(432,765521).$$
 Remove the red $2$ from position $(3,2)$, and insert $z' = y_4$ into the tableau
 $$T' = \ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{\rd 0}0{\rd 0}1,0{\rd 0}1,0 }$$
The result is
$$\psi_{431}(T',z') = \ytableausetup{boxsize=1.25em}
 \ytableausetup{aligntableaux=center}
 \ytableaushort
{{\rd 0}0{\rd 0}{\rd 0}1,0{\rd 0}1,{\rd 0}}$$
which is an element of $\p B(531,765521) \subseteq \p R(431,765521)$. Therefore the procedure terminates and returns this last tableau.
\end{example}


\begin{theorem} \label{repeated}
 The repeated insertion process described above always terminates and is a weight-preserving bijection
 $$\Psi_{\mu,\lambda} \colon \p B(\mu,\lambda) \times \p W(\mu,\lambda) \longrightarrow \bigcup_{\nu} \p B(\nu,\lambda),$$
 where the union is over all partitions $\nu$ which cover $\mu$ and are contained in $\lambda$.
\end{theorem}

This proves \eqref{eqmain} and hence the hook-length formula for skew shapes, equation \eqref{eq}.

\section{Final remarks} \label{final}

\textbf{Comparison of Naruse's formula with others.} Naruse's formula seems better for many applications, e.g.~asymptotics; see for example \cite[Section 9]{mpp} and \cite{mppasymp}. This extended abstract presents another advantage: it has a natural bijective proof.

\smallskip

\noindent
\textbf{Connection to Ikeda--Naruse's formula.} It was pointed out by Morales and Panova (personal communicatio) that in \cite[equation (5.2)]{IN1}, Ikeda and Naruse proved algebraically that for a skew shape $\lambda/\mu$ that fits inside a $d \times (n-d)$ box, $(F(\lambda/1) - F(\mu/1)) F(\lambda/\mu) = \sum_{\mu \lessdot \nu \subseteq \lambda} F(\lambda/\nu)$, where $F(\lambda/\mu) = \sum_{D \in \p E(\lambda/\mu)} \prod_{(i,j) \in D} (z_{\lambda_i + d - i + 1} - z_{d+j-\lambda'_j})$. In particular, $F(\lambda/1) = \sum_{i = 1}^{r(\lambda)} (z_{\lambda_i + d - i + 1} - z_{d+j-\lambda'_j})$. For $n$ and $d$ fixed, we introduce variables $x_{\lambda_i-i} = z_{\lambda_i+d-i+1}$, $1 \leq i \leq d$, and $y_{\lambda'_j-j} = -z_{d+j-\lambda'_j}$, $1 \leq j \leq n-d$ (we always have $\lambda_i+d-i+1 \neq d+j-\lambda'_j$ since the difference is the hook length of the cell $(i,j)$), and get precisely \eqref{eqmain}.

\smallskip

\noindent
\textbf{Bijective proof of Monk's formula.} It was pointed out by Sara Billey that formula \eqref{eqmain} is similar to the Monk's formula for Schubert polynomials. Indeed, the double Schubert polynomial of a permutation $w$ is the sum over all RC-graphs $D$ for $w$  taking $\prod_{(i,j) \in D} (x_i +y_j)$. It would be interesting to see if there is a connection between our bijection and the bijective proof of Monk's formula from \cite{bergeronbilley}.

\smallskip

\noindent
\textbf{Shifted skew shapes.} An obvious open question is how to adapt the bijection to prove the version of Naruse's hook-length formula for \emph{shifted} skew shapes. One would expect that a version of such a bijection exists and is much more complicated than the one presented here. It would be interesting to compare the level of difficulty with bijective proofs of the usual hook-length formula for shifted shapes, see e.g.~\cite{fischer} and \cite{kon}.

%\section*{Acknowledgments}

\acknowledgements{The author would like to thank Alejandro Morales, Igor Pak and Greta Panova for telling him about the problem and the interesting discussions that followed. Many thanks also to Sara Billey for reading an early draft of \cite{excited} so carefully and for giving numerous useful suggestions, and to Graham Gordon for finding a typo in \eqref{oo}.}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography
%\bibliographystyle{siam}
%\bibliography{  bibl}



\end{document}
