%% 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{78}
%% 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Environments 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  MACROS for this particular document
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\SSCT}{\ensuremath\mathrm{SSCT}}
\newcommand{\SSKT}{\ensuremath\mathrm{SSKT}}
\newcommand{\KD}{\ensuremath\mathrm{KD}}
\newcommand{\YRD}{\ensuremath\mathrm{YRD}}

\newcommand{\wt}{\ensuremath\mathrm{\mathbf{wt}}}%{\mathbf{wt}}

\newcommand{\drop}{\ensuremath\mathrm{drop}}

\newcommand{\Row}{\ensuremath\mathrm{Row}}
\newcommand{\Comp}{\ensuremath\mathrm{Comp}}

\newcommand{\lswap}{\ensuremath\mathrm{lswap}}
\newcommand{\rectify}{\ensuremath\mathrm{rectify}}
\newcommand{\addable}{\ensuremath\mathrm{addable}}

\newcommand{\key}{\ensuremath\kappa}
\newcommand{\schubert}{\ensuremath\mathfrak{S}}

\newcommand{\comp}[1]{\mathbf{#1}}
\newcommand{\Perm}{\mathcal{S}}
\newcommand{\Z}{\mathbf{Z}}

\newcommand{\inv}{\mathrm{inv}}
\newcommand{\sgn}{\mathrm{sgn}}
\newcommand{\diagram}{\mathbf{D}}

%%%%%%%%%%%%%%%%%%%%%%
% macreau for tableaux
%%%%%%%%%%%%%%%%%%%%%%
\newlength\cellsize \setlength\cellsize{10\unitlength}

\savebox2{%
\begin{picture}(10,10)
\put(0,0){\line(1,0){10}}
\put(0,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\line(1,0){10}}
\end{picture}}

\newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}%
\ifx\thearg\nothing\vrule width0pt height\cellsize depth0pt%
  \else\hbox to 0pt{\usebox2\hss}\fi%
  \vbox to 10\unitlength{\vss\hbox to 10\unitlength{\hss$#1$\hss}\vss}}

\newcommand\tableau[1]{\vtop{\let\\=\cr
\setlength\baselineskip{-10000pt}
\setlength\lineskiplimit{10000pt}
\setlength\lineskip{0pt}
\halign{&\cellify{##}\cr#1\crcr}}}

\definecolor{boxgray}{gray}{.7}
\newcommand{\cb}{\color{boxgray}\rule{1\cellsize}{1\cellsize}\hspace{-\cellsize}\usebox2}


%% define your title in the usual way
\title{A Pieri rule for key polynomials}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sami Assaf\thanks{\href{mailto:shassaf@usc.edu}{shassaf@usc.edu}. Work supported by a grant from the Simons Foundation (Award 524477, S.A.).}\addressmark{1} \and Danjoseph Quijada\thanks{\href{mailto:dquijada@usc.edu}{dquijada@usc.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}University of Southern California, 3620 S. Vermont Ave., Los Angeles, CA 90089-2532 USA}

%% 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{We conjecture a cancellation-free expansion for the product of a key polynomial and a single row key polynomial, generalizing Pieri's rule for computing the product of a Schur function with a single row Schur function.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{French version here (or omit).}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Demazure characters, key polynomials, Kohnert diagrams, Pieri rule}

%% 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{78-Assaf-Quijada}
%% 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{sec:introduction}


Schur polynomials are ubiquitous throughout mathematics. In
representation theory they appear as irreducible characters for
polynomial representations of the general linear group and in geometry as
polynomial representatives for the cohomology classes of Schubert cycles
in Grassmannians. In both contexts, combinatorial rules for expanding the
product of Schur polynomials in the Schur basis have deep meaning, in the
former case giving the irreducible decomposition of tensor products of
modules and in the latter case giving intersection numbers for Grassmannian Schubert varieties. The celebrated Pieri rule \cite{Pie93} computes these structure constants when one of the factors has a special form, namely the indexing partition has a single nonzero part.

Demazure \cite{Dem74} generalized the Weyl character formula to certain submodules generated by extremal weight spaces under the action of a Borel subalgebra of a Lie algebra. These \emph{Demazure characters} originally arose in connection with Schubert calculus \cite{Dem74a}, and, in the case of the general linear group, form a basis of the polynomial ring often called \emph{key polynomials}. Therefore we may consider the expansion of a product of key polynomials into the key basis. However, while the coefficients that appear have interpretations in representation theory and geometry, they are not, in general, non-negative. In this abstract, we conjecture a combinatorial rule for computing these structure constants when one of the factors has a special form parallel to the Pieri case for Schur polynomials, namely the indexing weak composition has a single nonzero part.

Toward a proof of our formula, Pieri's rule for key polynomials, we
generalize the combinatorial proof of Pieri's rule for Schur polynomials
using Robinson--Schensted insertion \cite{Rob38,Sch61}. Moreover, we prove that the signs that arise in the key case do so naturally from taking cardinalities of unions of overlapping sets, suggesting that while the rule is not non-negative, it still has significant combinatorial and geometric content. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Pieri rule for Schur polynomials}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:schur}

A \emph{partition} $\lambda$ of $m$ is a sequence $(\lambda_1 \geq \cdots \geq \lambda_{\ell} > 0)$ of positive integers that sum to $m$. Partitions of length at most $n$ naturally index a basis for symmetric polynomials in $n$ variables. We draw the \emph{diagram} of a partition $\lambda$ in English notation as the set of left justified cells with $\lambda_{i}$ cells in row $i$ from the top. For example, Figure~\ref{fig:5441} shows the diagram for $(5,4,4,1)$.

\begin{figure}[ht]
  \begin{center}
    $\tableau{ \ & \ & \ & \ & \ \\
      \ & \ & \ & \ \\
      \ & \ & \ & \ \\
      \ }$
  \caption{\label{fig:5441} The diagram for the partition $(5,4,4,1)$.}
  \end{center}
\end{figure}


\begin{definition}
  The \emph{semi-standard contratableaux of shape $\lambda$}, denoted by $\SSCT_n(\lambda)$, are maps $T$ from cells of the diagram of $\lambda$ to $\{1,2,\ldots,n\}$ such that
  \begin{itemize}%\addtolength{\itemsep}{-0.5\baselineskip}
  \item $T(c) \geq T(d)$ if $c,d$ are cells in the same row of $\lambda$ with $c$ left of $d$, and 
  \item $T(c) > T(d)$ if $c,d$ are cells in the same column of $\lambda$ with $c$ above $d$.
  \end{itemize}
  \label{def:SSCT}
\end{definition}

For example, the set $\SSCT_3(3,2)$ is shown in Figure~\ref{fig:SSCT}.

\iffalse
\begin{figure}[ht]
  \begin{center}
    $\begin{array}{cccccccc}
      \tableau{1 & 1 & 1 \\ 2 & 2 } &
      \tableau{1 & 1 & 1 \\ 2 & 3 } &
      \tableau{1 & 1 & 1 \\ 3 & 3 } &
      \tableau{1 & 1 & 2 \\ 2 & 2 } &
      \tableau{1 & 1 & 3 \\ 2 & 2 } &
      \tableau{1 & 1 & 2 \\ 2 & 3 } &
      \tableau{1 & 1 & 2 \\ 3 & 3 } &
      \tableau{1 & 1 & 3 \\ 2 & 3 } \\[1.5\cellsize]
      \tableau{1 & 1 & 3 \\ 3 & 3 } &
      \tableau{1 & 2 & 2 \\ 2 & 3 } &
      \tableau{1 & 2 & 2 \\ 3 & 3 } &
      \tableau{1 & 2 & 3 \\ 2 & 3 } &
      \tableau{1 & 2 & 3 \\ 3 & 3 } &
      \tableau{2 & 2 & 2 \\ 3 & 3 } &
      \tableau{2 & 2 & 3 \\ 3 & 3 } 
    \end{array}$
  \caption{\label{fig:SSYT}The set $\SSCT_3(3,2)$ of semi-standard contratableaux of shape $(3,2)$.}
  \end{center}
\end{figure}
\fi

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{cccccccc}
      \tableau{3 & 3 & 3 \\ 2 & 2} &
      \tableau{3 & 3 & 3 \\ 2 & 1} &
      \tableau{3 & 3 & 3 \\ 1 & 1} &
      \tableau{3 & 3 & 2 \\ 2 & 2} &
      \tableau{3 & 3 & 1 \\ 2 & 2} &
      \tableau{3 & 3 & 2 \\ 2 & 1} &
      \tableau{3 & 3 & 2 \\ 1 & 1} &
      \tableau{3 & 3 & 1 \\ 2 & 1} \\ \\%[1.5\cellsize]
      \tableau{3 & 3 & 1 \\ 1 & 1} &
      \tableau{3 & 2 & 2 \\ 2 & 1} &
      \tableau{3 & 2 & 2 \\ 1 & 1} &
      \tableau{3 & 2 & 1 \\ 2 & 1} &
      \tableau{3 & 2 & 1 \\ 1 & 1} &
      \tableau{2 & 2 & 2 \\ 1 & 1} &
      \tableau{2 & 2 & 1 \\ 1 & 1} 
    \end{array}
  \end{displaymath}
  \caption{\label{fig:SSCT}The set $\SSCT_3(3,2)$ of semi-standard contratableaux of shape $(3,2)$.}
\end{figure}

A \emph{weak composition} is a sequence of non-negative integers. To each semi-standard contratableau $T$, we associate the weak composition $\wt(T)$ whose $i$th component is equal to the number of occurrences of $i$ in $T$. For example, the weights of the first column of tableaux in Figure~\ref{fig:SSCT} are $(0,2,3),(3,0,2)$, from top to bottom.

Schur polynomials form an important basis of symmetric polynomials. They can be defined as the generating polynomials for semi-standard contratableaux as follows.

\begin{definition}
  The \emph{Schur polynomial} $s_{\lambda}(x_1,\ldots,x_n)$ is given by
  \begin{equation}
    s_{\lambda}(x_1,\ldots,x_n) = \sum_{T \in \SSCT_n(\lambda)} x_1^{\wt(T)_1} \cdots x_n^{\wt(T)_n}.
    \label{e:schur}
  \end{equation}
  \label{def:schur}
\end{definition}

For example, from Figure~\ref{fig:SSCT} we can compute the Schur polynomial
\begin{eqnarray*}
  s_{(3,2)}(x_1,x_2,x_3) & = & x_2^2 x_3^3 + x_1 x_2 x_3^3 + x_1^2 x_3^3 + x_2^3 x_3^2 + 2 x_1 x_2^2 x_3^2 + x_1^2 x_2 x_3^2 + x_1^2 x_2 x_3^2 \\
  & & + x_1^3 x_3^2 + x_1 x_2^3 x_3 + 2 x_1^2 x_2^2 x_3 + x_1^3 x_2 x_3 + x_1^2 x_2^3 + x_1^3 x_2^2.
\end{eqnarray*}

The celebrated Pieri rule \cite{Pie93}, originally stated in the context of Schubert Calculus, gives an elegant rule for expanding the product $s_{\lambda} s_{(m)}$ in the Schur basis. For a partition $\lambda$, we may add a cell to $\lambda$ if the result is again the diagram of a partition. For example, the addable cells for the partition $(5,4,4,1)$ are illustrated in Figure~\ref{fig:add-part}.

\begin{figure}[ht]
  \begin{center}
    $\begin{array}{cccc}
      \tableau{
        \ & \ & \ & \ & \ & \\
        \ & \ & \ & \ & \\
        \ & \ & \ & \ \\
        \ &  \\
        \cb } &
      \tableau{
        \ & \ & \ & \ & \ & \\
        \ & \ & \ & \ & \\
        \ & \ & \ & \ \\
        \ & \cb } &
      \tableau{
        \ & \ & \ & \ & \ & \\
        \ & \ & \ & \ & \cb\\
        \ & \ & \ & \ \\
        \ & } &
      \tableau{
        \ & \ & \ & \ & \ & \cb \\
        \ & \ & \ & \ & \\
        \ & \ & \ & \ \\
        \ & }
    \end{array}$
  \caption{\label{fig:add-part}An illustration of the four addable cells (shaded) for the partition $(5,4,4,1)$.}
  \end{center}
\end{figure}


Foreshadowing Pieri's rule stated below, compare Figure~\ref{fig:add-part} with the Schur expansion
\begin{displaymath}
  s_{(5,4,4,1)} s_{(1)} = s_{(5,4,4,1,1)} + s_{(5,4,4,2)} + s_{(5,5,4,1)} + s_{(6,4,4,1)}.
\end{displaymath}


Pieri's rule for Schur polynomials may be stated as the sum over all ways to add $m$ cells successively to $\lambda$ with no two cells added in the same column. If we add $m$ cells to $\lambda$ with no two in the same column, then we call these added cells a \emph{horizontal $m$-strip}.

\begin{theorem}[\cite{Pie93}]
  For a partition $\lambda$ and $m>0$ an integer, we have
  \begin{equation}
    s_{\lambda} s_{(m)} = \sum_{\mu/\lambda \ \mathrm{hor.} \ m-\mathrm{strip}} s_{\mu} ,
    \label{e:pieri}
  \end{equation}
  where $\mu/\lambda$ is the set-theoretic difference of the diagrams of $\mu$ and $\lambda$.
  \label{thm:pieri}
\end{theorem}


For example, Theorem~\ref{thm:pieri} gives the following expansion illustrated in Figure~\ref{fig:pieri}
\[ s_{(3,2,2)} s_{(2)} = s_{(3,2,2,2)} + s_{(3,3,2,1)} + s_{(4,2,2,1)} + s_{(4,3,2)} + s_{(5,2,2)}. \]

\begin{figure}[ht]
  \begin{center}
    $\tableau{\ & \ & \ \\ \ & \ \\ \ & \ } \ \raisebox{-1\cellsize}{$\times$} \
    \tableau{\cb & \cb \\ \\ } \ \raisebox{-1\cellsize}{$=$} \
    \tableau{\ & \ & \ \\ \ & \ \\ \ & \ \\ \cb & \cb  } \ \raisebox{-1\cellsize}{$+$} \
    \tableau{\ & \ & \ \\ \ & \ & \cb \\ \ & \ \\ \cb & } \ \raisebox{-1\cellsize}{$+$} \
    \tableau{\ & \ & \ & \cb \\ \ & \ \\ \ & \ \\ \cb & } \ \raisebox{-1\cellsize}{$+$} \
    \tableau{\ & \ & \ & \cb \\ \ & \ & \cb \\ \ & \ } \ \raisebox{-1\cellsize}{$+$} \
    \tableau{\ & \ & \ & \cb & \cb \\ \ & \ \\ \ & \ } $
  \caption{\label{fig:pieri}An illustration of the Pieri rule for computing the product $s_{(3,2,2)} s_{(2)}$.}
  \end{center}
\end{figure}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Key polynomials}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:key}

As is the case for any basis of the full polynomial ring, key polynomials are indexed by weak compositions. Just as with the Schurs, the keys may be defined diagrammatically, however now instead of changing the number within cells we instead allow the cells to move. In this and the following sections, we shall adopt coordinate notation in which row and column indices of cells are increasing going to the right and up. The reason for this shift from Section 2 will be made apparent shortly. 

Given a weak composition $\comp{a}=(a_1,\ldots,a_{n})$, we draw the \emph{key diagram} of $\comp{a}$ as the set of left justified cells with $a_i$ cells in row $i$. For example, Figure~\ref{fig:40514} shows the key diagram for $(4,1,5,0,4)$. 

\begin{figure}[ht]
  \begin{displaymath}
    \vline\tableau{ \ & \ & \ & \ \\
      \\
      \ & \ & \ & \ & \ \\
      \ \\
      \ & \ & \ & \  } 
  \end{displaymath}
  \caption{\label{fig:40514} The diagram for the weak composition $(4,1,5,0,4)$.}
\end{figure}

Note, given a fixed positive integer $n$, the diagram of a partition $\lambda$ is the same as the key diagram of the weak composition $(0,\ldots,0,\lambda_{\ell},\ldots,\lambda_1)$ of length $n$. For example, Figure~\ref{fig:5441} also shows the diagram of $(0,1,4,4,5)$.

Kohnert \cite{Koh91} gave an elegant rule for computing a key polynomial based on diagrams.

\begin{definition}[\cite{Koh91}]
  A \emph{Kohnert move} on a diagram moves the rightmost cell of a given row to the highest empty position below it in the same column, jumping over other cells in its way as needed. The set of diagrams obtained by Kohnert moves from the key diagram of $\comp{a}$ is $\KD(\comp{a})$.
\label{def:move}
\end{definition}

For example, Figure~\ref{fig:KT} shows the Kohnert diagrams for $(0,3,2)$. 

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{ccccccccc}
      \vline\tableau{ \times & \times \\ \times & \times & \times \\  } &
      \vline\tableau{ \times & \times \\ \times & \times  \\ & & \times } &
      \vline\tableau{ \times & \times \\ \times \\ & \times & \times  } &
      \vline\tableau{ \times & \times \\ \\ \times & \times & \times  } &
      \vline\tableau{ \times \\ \times & \times \\ & \times & \times } & 
      \vline\tableau{ \times \\ & \times \\ \times & \times & \times } &
      \vline\tableau{ \\ \times & \times \\ \times & \times & \times } &
      \vline\tableau{ \times \\ \times & \times & \times \\ & \times } &
      \vline\tableau{  \\ \times & \times & \times \\ \times & \times }        
    \end{array}
  \end{displaymath}
  \caption{\label{fig:KT}The set $\KD(0,3,2)$ of Kohnert diagrams for $(0,3,2)$.}
\end{figure}

Key polynomials, studied combinatorially by Lascoux and Sch{\"u}tzenberger \cite{LS90}, Kohnert \cite{Koh91}, Reiner and Shimozono \cite{RS95}, Mason \cite{Mas06,Mas09}, Assaf and Searles \cite{AS18}, and others, can be characterized analogously to Schur polynomials as the generating polynomial for Kohnert diagrams of a key diagram.

\begin{theorem}[\cite{Koh91}]
  The key polynomial $\key_{\comp{a}}$ is given by
  \begin{equation}
    \key_{\comp{a}}(x) = \sum_{T \in \KD(\comp{a})} x_1^{\wt(T)_1} \cdots x_n^{\wt(T)_n} ,
    \label{e:key}
  \end{equation}
  where $\wt(T)$ is the weak composition whose $i$th part is the number of cells in row $i$ of $T$.
  \label{thm:key-SSKT}  
\end{theorem}

For example, from Figure~\ref{fig:KT} we can compute
\begin{displaymath}
  \key_{(0,3,2)} = x_2^3 x_3^2 + x_1 x_2^2 x_3^2 + x_1^2 x_2 x_3^2 + x_1^3 x_3^2 + x_1^2 x_2^2 x_3 + x_1^3 x_2 x_3 + x_1^3 x_2^2 + x_1 x_2^3 x_3 + x_1^2 x_2^3 .
\end{displaymath}

Key polynomials form a basis of the full polynomial ring that contains the Schur polynomials in the following sense.

\begin{proposition}[\cite{Mac91}]
  For $\comp{a}$ a weakly increasing sequence of length $n$, we have
  \begin{equation}
    \key_\comp{a} = s_{\mathrm{rev}(\comp{a})}(x_1,\ldots,x_n),
  \end{equation}
  where $\mathrm{rev}(\comp{a})$ is the partition $(a_n,a_{n-1},\ldots,a_1)$.
\end{proposition}

For example, $\key_{(0,2,3)} = s_{(3,2)}(x_1,x_2,x_3)$. Viewed diagrammatically, every semi-standard contratableau has a corresponding Kohnert diagram of the same weight obtained by moving each cell of the tableau down to the row prescribed by its entry. For example, compare Figure~\ref{fig:SSCT} with Figure~\ref{fig:KD}. Note that $\key_{(0,2,3)}$ is not equal to $\key_{(0,3,2)}$, as a comparison between Figures~\ref{fig:KT} and \ref{fig:KD} shows.

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{cccccccc}
%      \tableau{3 & 3 & 3 \\ 2 & 2} &
      \vline \vline\tableau{ \times & \times & \times \\ \times & \times \\  } &
%      \tableau{3 & 3 & 3 \\ 2 & 1} &
      \vline \vline\tableau{ \times & \times & \times \\ \times \\ & \times \\  } &
%      \tableau{3 & 3 & 3 \\ 1 & 1} &
      \vline \vline\tableau{ \times & \times & \times \\ \\ \times & \times \\  } &
%      \tableau{3 & 3 & 2 \\ 2 & 2} &
      \vline \vline\tableau{ \times & \times \\ \times & \times & \times \\  } &
%      \tableau{3 & 3 & 1 \\ 2 & 2} &
      \vline \vline\tableau{ \times & \times \\ \times & \times \\ & & \times  } &
%      \tableau{3 & 3 & 2 \\ 2 & 1} &
      \vline \vline\tableau{ \times & \times \\ \times & & \times \\ & \times  } &
%      \tableau{3 & 3 & 2 \\ 1 & 1} &
      \vline \vline\tableau{ \times & \times \\ & & \times \\ \times & \times  } &
%      \tableau{3 & 3 & 1 \\ 2 & 1} \\ \\%[1.5\cellsize]
      \vline \vline\tableau{ \times & \times \\ \times \\ & \times & \times  } \\ \\
%      \tableau{3 & 3 & 1 \\ 1 & 1} &
      \vline \vline\tableau{ \times & \times \\ \\ \times & \times & \times  } &
%      \tableau{3 & 2 & 2 \\ 2 & 1} &
      \vline \vline\tableau{ \times \\ \times & \times & \times \\ & \times  } &
%      \tableau{3 & 2 & 2 \\ 1 & 1} &
      \vline \vline\tableau{ \times \\ & \times & \times \\ \times & \times  } &
%      \tableau{3 & 2 & 1 \\ 2 & 1} &
      \vline \vline\tableau{ \times \\ \times & \times \\ & \times & \times  } &
%      \tableau{3 & 2 & 1 \\ 1 & 1} &
      \vline \vline\tableau{ \times \\ & \times \\ \times & \times & \times  } &
%      \tableau{2 & 2 & 2 \\ 1 & 1} &
      \vline \vline\tableau{ \\ \times & \times & \times \\ \times & \times  } &
%      \tableau{2 & 2 & 1 \\ 1 & 1} 
      \vline \vline\tableau{ \\ \times & \times \\ \times & \times & \times  }
    \end{array}
  \end{displaymath}
  \caption{The set $\KD(0,2,3)$ of diagrams obtained by Kohnert moves from the key diagram of weak composition $\comp{a} = (0,2,3)$.}
    \label{fig:KD}
\end{figure}

One might hope that the analog of Pieri's rule for key polynomials may be stated as the sum over all ways to add $m$ cells successively to $\comp{a}$ with no two cells added in the same column. However, the rule has two subtleties that complicate this simple idea, both of which are best demonstrated by example. 

Consider the following expansion illustrated diagrammatically in Figure~\ref{fig:pierikey},
\begin{eqnarray*}
  \key_{(2,0,3,2)} \key_{(0,0,2)} & = & \key_{(2,2,3,2)} + \key_{(2,3,3,1)} + \key_{(3,1,3,2)} - \key_{(2,2,3,1)} + \key_{(2,1,4,2)} \\
  & & + \key_{(3,0,4,2)} + \key_{(2,3,4)} - \key_{(3,2,4)} + \key_{(2,0,5,2)}.
\end{eqnarray*}

\begin{figure}[ht]
  \begin{eqnarray*}
    \vline\tableau{ \ & \ \\ \ & \ & \ \\ \\ \ & \ } \ \raisebox{-1\cellsize}{$\times$} \
    \vline\tableau{\\ \cb & \cb \\ \\  } & = &
    \vline\tableau{ \ & \ \\ \ & \ & \ \\ \cb & \cb \\ \ & \ } \ \raisebox{-1\cellsize}{$+$} \
    \vline\tableau{ \ \\ \ & \ & \ \\ \cb & \times & \cb \\ \ & \ } \ \raisebox{-1\cellsize}{$+$} \
    \vline\tableau{ \ & \ \\ \ & \ & \ \\ \cb \\ \ & \ & \cb } \ \raisebox{-1\cellsize}{$-$} \
    \vline\tableau{ \ \\ \ & \ & \ \\ \cb & \times \\ \ & \ & \cb } \ \raisebox{-1\cellsize}{$+$} \
    \vline\tableau{ \ & \ \\ \ & \ & \ & \cb \\ \cb \\ \ & \ } \\
    & & \raisebox{-1\cellsize}{$+$} \
    \vline\tableau{ \ & \ \\ \ & \ & \ & \cb \\ \\ \ & \ & \cb } \ \raisebox{-1\cellsize}{$+$} \
    \vline\tableau{ \\ \ & \ & \ & \cb \\ \times & \times & \cb \\ \ & \ } \ \raisebox{-1\cellsize}{$-$} \
    \vline\tableau{ \\ \ & \ & \ & \cb \\ \times & \times \\ \ & \ & \cb } \ \raisebox{-1\cellsize}{$+$} \
    \vline\tableau{ \ & \ \\ \ & \ & \ & \cb & \cb \\ \\ \ & \ } 
  \end{eqnarray*}
  \caption{\label{fig:pierikey}An illustration of the Pieri rule computing the product $\key_{(2,0,3,2)} \key_{(0,0,2)}$.}
\end{figure}

Here we take $\comp{a} = (2,0,3,2)$ and $m=2$. We see that the terms in the key expansion are obtained by adding $2$ cells to $\comp{a}$ \emph{after possibly moving cells down}. In Figure~\ref{fig:pierikey}, the added cells are shaded and the moved cells are indicated with crosses. The auxiliary step of cells moving down results from applying a \emph{restricted} insertion algorithm that forbids us from adding a cell above a given row $k$, with $k=3$ in the example. Additionally, some terms appear with a negative sign. These signs result from the insertion algorithm establishing a bijection between products of Kohnert diagrams (on the left) and unions of Kohnert diagrams (on the right) where the unions are \emph{not disjoint}. Therefore the signs arise from the inclusion--exclusion formula for computing the cardinality of a union of sets as an alternating sum of cardinalities of intersections.

A precise formula requires additional notation presented in the sections to follow.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Insertion algorithms}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:insert}

An elegant combinatorial proof of Pieri's rule for Schur polynomials
comes from using the Robinson--Schensted correspondence \cite{Rob38,Sch61} to construct a bijection on tableaux
\begin{equation}
  \SSCT_n(\lambda) \times \SSCT_n((m)) \stackrel{\sim}{\longrightarrow} \bigsqcup_{\mu / \lambda \ \mathrm{hor.} \ m-\mathrm{strip}} \SSCT_n(\mu) ,
  \label{e:RSK}
\end{equation}
where the sum is over all horizontal $m$-strips for $\lambda$. Note that the union on the right is \emph{disjoint}, and so \eqref{e:pieri} follows immediately from this bijection and Definition~\ref{def:schur}.

Our approach to the Pieri rule for key polynomials comes via a similar
insertion algorithm that generalizes the Robinson--Schensted correspondence to Kohnert diagrams. There is one key difference when generalizing insertion in this context. Each semi-standard contratableau has a unique shape evident from the tableau. In contrast, a diagram can arise as a Kohnert diagram for many different key diagrams, and so there is no immediate way to determine the corresponding shape.

Indeed, for any pair of weak compositions $\comp{a}$ and $\comp{b}$, $\KD(\comp{b}) \subset \KD(\comp{a})$ if and only if the key diagram of $\comp{b}$ can be obtained by Kohnert moves on the key diagram of $\comp{a}$. In this sense we ascribe a poset structure on the set of weak compositions by writing $\comp{b} \prec \comp{a}$. One can visualize $\comp{b} \prec \comp{a}$ as dropping some of the cells in the key diagram of $\comp{a}$ to obtain the key diagram of $\comp{b}$. For example, $(5,4,5,0,1) \prec (5,1,5,0,4)$, as illustrated in Figure~\ref{fig:poset}. 

%\begin{figure}[ht]
%\begin{center}
%  \begin{displaymath}
%    \begin{array}{cc}  
%      \vline\tableau{ \ & \times & \times & \times \\
%        \\
%        \ & \ & \ & \ & \ & \\
%        \ & & & & \\
%        \ & \ & \ & \ & \ } &
%      \vline\tableau{ \ & & & \\
%        \\
%        \ & \ & \ & \ & \ & \\
%        \ & \ & \ & \ & \times \\
%        \ & \ & \ & \ & } \\ \\
%      \vline\tableau{ \ & & & \\
%        \\
%        \ & \ & \ & \ & \ & \\
%        \ & \times & \times & \times &  \\
%        \ & \ & \ & \ & \ } &
%      \vline\tableau{ \ & & & \\
%        \\
%        \ & \ & \ & \ & \ & \\
%        \ & \ & \ & \ &  \\
%        \ & \ & \ & \ & \times } 
%    \end{array}
%  \end{displaymath}
%\end{center}
%  \caption{\label{fig:poset} Visualizing $(5,1,5,0,4) \leq (5,4,5,0,1)$ in the first column of diagrams and $(4,5,5,0,1) \leq (5,4,5,0,1)$ in the second column. Cells that `drop down' are marked by $\times$. The weak compositions $(5,1,5,0,4)$ and $(5,4,5,0,1)$ are not comparable.}
%\end{figure}  
\begin{figure}[ht]
\begin{center}
  \begin{displaymath}
    \begin{array}{ccccc}  
      \vline\tableau{ \ & \times & \times & \times \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & & & & \\
        \ & \ & \ & \ & \ } & & & &
      \vline\tableau{ \ & & & \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \ & \ & \ & + \\
        \ & \ & \ & \ & } \\
      & \searrow & & \swarrow & \\
      & &
      \vline\tableau{ \ & & & \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \times & \times & \times &  \\
        \ & \ & \ & \ & + }
    \end{array}
  \end{displaymath}
\end{center}
  \caption{\label{fig:poset} Illustration of the relationships between $(5,1,5,0,4)$, $(4,5,5,0,1)$, and $(5,4,5,0,1)$. Cells that `drop down' from $(5,1,5,0,4)$ to $(5,4,5,0,1)$ are marked by $\times$ while cells that `drop down' from $(4,5,5,0,1)$ to $(5,4,5,0,1)$ are marked by $+$. The weak compositions $(5,1,5,0,4)$ and $(5,4,5,0,1)$ are not comparable in the poset.}
\end{figure}

For a weak composition $\comp{a}$ and positive integer $k$, we have an explicit insertion algorithm on Kohnert diagrams that we conjecture establishes the following weight-preserving bijection
\begin{equation}
  \KD(\comp{a}) \times \KD(0^{k-1}, 1) \stackrel{\sim}{\longrightarrow} \bigcup_{\substack{\comp{b} \preceq \comp{a} \\ j \leq k}} \KD(\comp{b} + (0^{j-1},1)),
  \label{e:biject}
  \end{equation}
where addition of weak compositions is defined coordinate-wise.

Diagrammatically, the indexing set of weak compositions in the image of \eqref{e:biject} can be understood as all the weak compositions whose key diagrams are obtained by dropping some cells in the key diagram of $\comp{a}$ and then appending a cell to a row of index $\leq k$.

Given the aforementioned containment of sets of Kohnert diagrams, we can trim this indexing set by considering only the weak compositions that are maximal in the poset structure. For example, if $\comp{a} = (4,1,5,0,4)$ and $k = 3$, then the maximal elements are $(4,2,5,0,4), (5,1,5,0,4), (4,5,5,0,1), (4,1,6,0,4)$. We therefore have the bijection
\begin{equation}
  \begin{split}
    \KD(4,1,5,0,4)& \times \KD(0,0,1) \stackrel{\sim}{\longrightarrow}\\
    &\KD(4,2,5,0,4) \cup \KD(5,1,5,0,4) \cup \KD(4,5,5,0,1) \cup \KD(4,1,6,0,4).
  \end{split}
  \label{e:minimal}
\end{equation}
We illustrate this example diagrammatically in Figure~\ref{fig:minimal}.

\begin{figure}[ht]
  \begin{eqnarray*}
     \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & & & & \\
        \ & \ & \ & \ & } 
     \raisebox{-2\cellsize}{$\times$} \
     \vline\tableau{\\ \\ \cb & \\}
     \raisebox{-2\cellsize}{$\stackrel{\sim}{\longrightarrow}$} \
     \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \cb & & & \\
        \ & \ & \ & \ & }
     \raisebox{-2\cellsize}{$\bigcup$} \
      \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & & & & \\
        \ & \ & \ & \ & \cb }
     \raisebox{-2\cellsize}{$\bigcup$} \
      \vline\tableau{ \ & & & \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \times & \times & \times & \cb \\
        \ & \ & \ & \ & }
     \raisebox{-2\cellsize}{$\bigcup$} \
      \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \cb \\
        \ & & & & \\
        \ & \ & \ & \ & }
  \end{eqnarray*}
  \caption{\label{fig:minimal} An illustration of the Pieri rule for computing the product $\key_{(4,1,5,0,4)} \key_{(0,0,1,0,0)}$.}
\end{figure} 

Given the set of weak compositions endowed with our poset structure, the subset of all weak compositions that rearrange to the same partition in fact form a lattice. Diagrammatically, the meet $\comp{a} \wedge \comp{b}$ of weak compositions $\comp{a}$ and $\comp{b}$ that sort to the same partition is given by the weak composition whose key diagram can be obtained from both $\comp{a}$ and $\comp{b}$ by moving the least number of cells down. For example,
\begin{displaymath}
(5,1,5,0,4) \wedge (4,5,5,0,1) = (5,4,5,0,1),
\end{displaymath}
as illustrated in Figure~\ref{fig:poset}. We then have the following.

\begin{theorem}
  Given weak compositions $\comp{a_1}, \ldots, \comp{a_p}$ that all sort to the same partition, we have
  \begin{equation}
    \KD(\comp{a_1}) \cap \cdots \cap \KD(\comp{a_p}) = \KD(\comp{a_1} \wedge \cdots \wedge \comp{a_p})
  \end{equation}
  \label{thm:union}
\end{theorem}

The signs in our key Pieri formula arise from the inclusion-exclusion phenomenon when taking cardinalities of unions that are not disjoint. Two maximal weak compositions in the image of \eqref{e:biject} rearrange to the same partition precisely when they result from adding cells in the same column. For example, only two of the maximal weak compositions in \eqref{e:minimal} sort to the same partition, namely $(5,1,5,0,4)$ and $(4,5,5,0,1)$, and both result from the addition of a cell in column $5$, as illustrated in Figure~\ref{fig:minimal}. The intersection of the Kohnert diagrams they generate is then given by
\begin{eqnarray*}
  \KD(5,1,5,0,4) \cap \KD(4,5,5,0,1) & = & \KD(5,4,5,0,1).
\end{eqnarray*}
Therefore taking the cardinality of the union of the Kohnert diagrams on the left gives an alternating formula. Translating this to a statement about generating polynomials, \eqref{e:minimal} yields the following key expansion,
\begin{displaymath}
  \overbrace{\key_{(4,1,5,0,4)} \key_{(0,0,1,0,0)}}^{\KD(4,1,5,0,4) \times \KD(0,0,1)} = \overbrace{\key_{(4,2,5,0,4)}}^{\KD(4,2,5,0,4)} + \overbrace{\key_{(5,1,5,0,4)} + \key_{(4,5,5,0,4)} - \key_{(5,4,5,0,1)}}^{\KD(5,1,5,0,4) \cup \KD(4,5,5,0,4)} + \overbrace{\key_{(4,1,6,0,4)}}^{\KD(4,1,6,0,4)}.
\end{displaymath}

Our full Pieri rule for key polynomials, stated in Conjecture~\ref{conj:monkey} below, follows from sequentially applying the algorithm that gives the conjectured bijection \eqref{e:biject} such that the added cells form a horizontal strip, and then applying Theorem~\ref{thm:union} when grouping the Kohnert diagrams into non-disjoint unions. We anticipate that the proof of Conjecture~\ref{conj:monkey} is forthcoming.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Pieri rule for key polynomials}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:pieri}

To state the Pieri rule for key polynomials explicitly, meaning to describe the compositions $\comp{b}$ and their corresponding signs appearing in the expansion
\begin{equation}
  \key_{\comp{a}} \key_{(0^{k-1},m)} = \sum_{\comp{b}} \sgn(\comp{b}) \key_{\comp{b}},
\end{equation}
we must generalize the notion of adding cells to include the notion of a bi-modal sequence with a valley at or before $k$ subject to certain additional constraints. 

\begin{definition}
  Let $\comp{a} = (a_1, a_2, \ldots)$ be a weak composition and let $k \geq 1$ be an integer. A \emph{$k$-restricted drop sequence $u$ of $\comp{a}$} is an increasing sequence of row indices
  $$(1 \leq r_{-s} < \cdots < r_{-1} < r_0 < r_1 < \cdots < r_t)$$
  for some non-negative integers $s,t$ such that:
  \begin{itemize}
  \item $a_{r_{-s}} > \cdots > a_{r_{-1}} > a_{r_0} < a_{r_1} < \cdots < a_{r_t}$ with $a_{r_{-s}} \leq a_{r_t}$;
  \item $r_0 \leq k < r_1$ (or simply $r_0 \leq k$ if $t=0$);
  \item for $i > 0$, if $r_{i-1} < r < r_i$, then either $r \leq r_{i-1}$ or $r>r_i$;
  \item for $-i < 0$, if $r_{-i} < r \leq k$, then either $a_{r} > a_{r_{-i}}, a_{r_t}$ or $a_{r} < a_{r_{-i}}, a_{r_t}$;
  \end{itemize} 
  We let $\sigma_u$ denote the permutation $(r_{-s}, \ldots, r_{-1}, r_0, r_1, \ldots, r_t)$ (in cycle form) and let $(c_u,r_u)$ denote the cell $(a_{r_t}+1,r_{-s})$. We also define $\sgn(u) = (-1)^s$.
  \label{def:drop-seq}
\end{definition}

We say that a cell $(c,r)$ is \emph{$k$-addable} to a weak composition $\comp{a}$ if $(c,r) = (c_u,r_u)$ for some $k$-restricted drop sequence $u$ of $\comp{a}$. In this context, the $k$-restricted drop sequence determines which cells move down to where they move, and the final row index in the sequence determines the row to which a cell is added. More precisely, we may then \emph{$k$-add} a cell $(c,r)$ to $\comp{a}$ in the following sense.

\begin{definition}
  Let $\comp{a} = (a_1, a_2, \ldots)$ be a weak composition and let $k \geq 1$ be an integer. Let $u$ be a $k$-restricted drop sequence of $\comp{a}$, and let $(c_u,r_u)$ be its associated $k$-addable cell. We say that a weak composition $\comp{b}$ is \emph{the $k$-addition} of $(c_u,r_u)$ to $\comp{a}$ by $u$ and write $\comp{a} \stackrel{u}{\longrightarrow} \comp{b}$ if $(c_u,r_u)$ is the set-theoretic difference between the key diagrams of $\comp{b}$ and $\sigma_u \cdot \comp{a}$.
\end{definition}

Here $\Perm_n$ acts on weak compositions of length $n$ by $\sigma \cdot
\comp{a} = (a_{\sigma(1)}, \ldots, a_{\sigma(n)})$. It is precisely this
action that induces the lattice structure on weak composition from
Section \ref{sec:insert}.

For example, let $\comp{a} = (4,1,5,0,4)$ and $k = 3$. The five $3$-restricted drop sequences of $(4,1,5,0,4)$ and their corresponding $3$-additions are illustrated in Figure~\ref{fig:addable}.

\begin{figure}[ht]
\begin{center}
  \begin{displaymath}
    \begin{array}{cccccc}
     u & (2) & (1) & (2,5) & (1,2,5) & (3) \\ \\
     \sgn(u) & + & + & + & - & + \\ \\
%     (c_u,r_u) & (2,2) & (1,5) & (1,5) & (2,5) & (6,3) \\
     \ \raisebox{-2\cellsize}{$\comp{a} \stackrel{u}{\longrightarrow} \comp{b}$} \  &  
     \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \cb & & & \\
        \ & \ & \ & \ & } &
      \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & & & & \\
        \ & \ & \ & \ & \cb } &
      \vline\tableau{ \ & \times & \times & \times \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & & & & \cb \\
        \ & \ & \ & \ & } &
      \vline\tableau{ \ & \times & \times & \times \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & & & & \\
        \ & \ & \ & \ & \cb } &
      \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \cb \\
        \ & & & & \\
        \ & \ & \ & \ & } \\ \\
     \ \raisebox{-2\cellsize}{$\comp{b}$} \  &  
     \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \cb & & & \\
        \ & \ & \ & \ & } &
      \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & & & & \\
        \ & \ & \ & \ & \cb } &
      \vline\tableau{ \ & & & \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \times & \times & \times & \cb \\
        \ & \ & \ & \ & } &
      \vline\tableau{ \ & & & \\
        \\
        \ & \ & \ & \ & \ & \\
        \ & \times & \times & \times &  \\
        \ & \ & \ & \ & \cb } &
      \vline\tableau{ \ & \ & \ & \ \\
        \\
        \ & \ & \ & \ & \ & \cb \\
        \ & & & & \\
        \ & \ & \ & \ & }
    \end{array}
  \end{displaymath}
\end{center}
  \caption{\label{fig:addable}The five ways to $3$-add a cell (shaded) to the weak composition $\comp{a}=(4,1,5,0,4)$. Cells that will `drop down' in the process of $3$-addition are marked with $\times$. The marked cells in the case $u = (2,5)$ in particular will end up supporting the shaded cell in $(5,2)$ when it is $3$-added to $\comp{a}$.}
\end{figure}

The simplest case of the Pieri rule for key polynomials, often called Monk's rule, can be stated as the \emph{signed sum} of all possible ways to $k$-add a single cell to $\comp{a}$. For example, compare Figure~\ref{fig:addable} to the key expansion
\begin{displaymath}
  \key_{(4,1,5,0,4)} \key_{(0,0,1,0,0)} = \key_{(4,2,5,0,4)} + \key_{(5,1,5,0,4)} + \key_{(4,5,5,0,4)} - \key_{(5,4,5,0,1)} + \key_{(4,1,6,0,4)}.
\end{displaymath}
Here the middle three terms on the right correspond to $3$-adding cells in column $5$. The $3$-addition $(5,4,5,0,1)$ comes with a negative sign because it is the meet of $(5,1,5,0,4)$ and $(4,5,5,0,1)$, as detailed earlier.

For the full Pieri rule, we iterate the $k$-addition of individual cells such that no two $k$-added cells lie in the same column, i.e. the $k$-added cells form a horizontal $m$-strip. For brevity, we let $m$ iterations of $k$-additions 
\begin{displaymath}
  \comp{a} = \comp{a_0} \stackrel{u_1}{\longrightarrow} \comp{a_1} \stackrel{u_2}{\longrightarrow} \comp{a_2} \stackrel{u_3}{\longrightarrow} \cdots \stackrel{u_m}{\longrightarrow} \comp{a_m} = \comp{b}
\end{displaymath}
be denoted by 
\begin{displaymath}
  \comp{a} \stackrel{\comp{U}}{\longrightarrow} \comp{b},
\end{displaymath}
where $\comp{U} = (u_1,u_2, \ldots, u_m)$ is a sequence of $k$-restricted drop sequences, and we set
\begin{equation}
  \sgn(\comp{U}) = \prod_{i=1}^m \sgn(u_i) .
  \label{e:sgn}
\end{equation}
Then $\comp{U}$ is a \emph{$k$-restricted horizontal $m$-strip} if no two $k$-added cells lie in the same column.

Note that it is possible to have $\comp{a} \stackrel{\comp{U}}{\longrightarrow} \comp{b}$ and $\comp{a} \stackrel{\comp{U'}}{\longrightarrow} \comp{b}$ for distinct $\comp{U}, \comp{U'}$. However, in that case the set of $k$-added cells will be the same for both sequences and $\sgn(\comp{U}) = \sgn(\comp{U'})$. We shall only count each $\comp{b}$ once with some choice of $k$-addition sequence in the Pieri rule for the keys, just as each partition is counted only once in the Pieri rule for Schurs. 

\begin{conjecture}
  Given a weak composition $\comp{a}$ and positive integers $k$ and $m$, we have
  \begin{equation}
    \key_{\comp{a}} \key_{(0^{k-1},m)} = \key_{\comp{a}} s_{(m)}(x_1, \ldots, x_k) = \sum_{\substack{\comp{a} \stackrel{\comp{U}}{\longrightarrow} \comp{b} \\ \comp{U} \mathrm{\ hor.\ }m-\mathrm{strip} }} \sgn(\comp{U}) \key_{\comp{b}} ,
  \label{e:monkey}
  \end{equation}
where the sum is over all weak compositions $\comp{b}$ that can be reached by $m$ successive iterations of $k$-additions to $\comp{a}$.
\label{conj:monkey}
\end{conjecture}

In particular, observe that the structure constants are all $\pm 1$. In the case when $\comp{a}$ is weakly increasing and $k$ is taken to be the length of $\comp{a}$, there is precisely one way to add a cell in any given column and we obtain Pieri's rule for Schur polynomials. More generally, the key Pieri rule gives non-negative expansions for the following cases for which we can prove that the rule holds.

\begin{theorem}
  Conjecture~\ref{conj:monkey} holds for a weak composition $\comp{a}$ and a positive integer $k$ such that $a_i=0$ for all $i>k$.
\end{theorem}

We have computer verified Conjecture~\ref{conj:monkey} for weak compositions $a$ of length up to $10$ and total size of $a$ plus $m$ up to $12$. 


%% 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



\end{document}
