%% 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{53}
%% 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{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{thm}[theorem]{Theorem}
\newtheorem{lem}[theorem]{Lemma}

\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
%\newtheorem{xca}[theorem]{Exercise}

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

\usepackage{lipsum}


\usepackage{tikz-cd}




\newtheorem*{thma}{Theorem A}
\newtheorem*{thmb}{Theorem B}
\newtheorem*{thmc}{Theorem C}
\newtheorem*{thmd}{Theorem D}


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

\newcommand{\SSYT}{\ensuremath{\mathrm{SSYT}}}
\newcommand{\QYT}{\ensuremath{\mathrm{QYT}}}
\newcommand{\SCT}{\ensuremath{\mathrm{SCT}}}

\newcommand{\KT}{\ensuremath{\mathrm{KT}}}
\newcommand{\QKT}{\ensuremath{\mathrm{QKT}}}
\newcommand{\qKT}{\ensuremath{\mathrm{qKT}}}
\newcommand{\QqKT}{\ensuremath{\mathrm{QqKT}}}
\newcommand{\HqKT}{\ensuremath{\mathrm{HqKT}}}
\newcommand{\LRS}{\ensuremath{\mathrm{LRS}}}
\newcommand{\HLRS}{\ensuremath{\mathrm{HLRS}}}


\newcommand{\SSF}{\ensuremath{\mathrm{SSF}}}
\newcommand{\ASSF}{\atom\ensuremath{\mathrm{SSF}}}
\newcommand{\MSSF}{\Mono\ensuremath{\mathrm{SSF}}}
\newcommand{\FSSF}{\Fund\ensuremath{\mathrm{SSF}}}
\newcommand{\LSSF}{\Part\ensuremath{\mathrm{SSF}}}
\newcommand{\HSSF}{\ensuremath{\mathrm{HSSF}}}



\newcommand{\SSAF}{\ensuremath{\mathrm{SSAF}}}
%\newcommand{\HSSF}{\ensuremath{\mathrm{HSSF}}}
\newcommand{\QSSF}{\ensuremath{\mathrm{QSSF}}}
%\newcommand{\SSPF}{\ensuremath{\mathrm{SSPF}}}
\newcommand{\revSSYT}{\ensuremath{\mathrm{revSSYT}}}
\newcommand{\Pairs}{\ensuremath{\mathrm{Pairs}}}
\newcommand{\HPairs}{\ensuremath{\mathrm{HPairs}}}
\newcommand{\HrevSSYT}{\ensuremath{\mathrm{HrevSSYT}}}
\newcommand{\QrevSSYT}{\ensuremath{\mathrm{QrevSSYT}}}


\newcommand{\KM}{\ensuremath{\mathrm{KM}}}

\newcommand{\FS}{\ensuremath{\mathrm{FS}}}


\newcommand{\wt}{\ensuremath{\mathrm{wt}}}
\newcommand{\destand}{\ensuremath{\mathrm{dst}}}

\newcommand{\sch}{\ensuremath{\mathfrak{S}}}
\newcommand{\key}{\ensuremath{\kappa}}
\newcommand{\qkey}{\ensuremath{\mathfrak{Q}}}
\newcommand{\Fund}{\ensuremath{\mathfrak{F}}}
\newcommand{\Mono}{\ensuremath{\mathfrak{M}}}
\newcommand{\Part}{\ensuremath{\mathfrak{L}}}
\newcommand{\atom}{\ensuremath{\mathcal{A}}}


\newcommand{\qeta}{\ensuremath{\hat{\eta}}}

\newcommand{\flatten}{\ensuremath{\mathrm{flat}}}
\newcommand{\sort}{\ensuremath{\mathrm{sort}}}
\newcommand{\rev}{\ensuremath{\mathrm{rev}}}
\newcommand{\swap}{\ensuremath{\mathrm{swap}}}
\newcommand{\Shuffle}{\ensuremath{\mathrm{Shuffle}}}



\newcommand{\lflat}{\ensuremath{\mathrm{lflat}}}
\newcommand{\lswap}{\ensuremath{\mathrm{lswap}}}
\newcommand{\Qlswap}{\ensuremath{\mathrm{Qlswap}}}


\newcommand{\covers}{\ensuremath{\rhd}}
\newcommand{\sgeq}{\ensuremath{\unrhd}}


\newcommand{\Des}{\ensuremath{\mathrm{Des}}}

\newcommand{\excise}[1]{}%{$\star$\textsc{#1}$\star$}


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

\savebox2{%
\begin{picture}(12,12)
\put(0,0){\line(1,0){12}}
\put(0,0){\line(0,1){12}}
\put(12,0){\line(0,1){12}}
\put(0,12){\line(1,0){12}}
\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 12\unitlength{\vss\hbox to 12\unitlength{\hss$#1$\hss}\vss}}

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

\newcommand{\e}{\mbox{}}






%% define your title in the usual way
\title{Combinatorial bases of polynomials}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Dominic Searles\thanks{\href{mailto:dominic.searles@otago.ac.nz}{dominic.searles@otago.ac.nz}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, University of Otago, Dunedin 9016}
%% put the date of submission here
\received{November 13, 2017}

%% leave this blank until submitting a revised version
\revised{March 28, 2018}

%% 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 establish a poset structure on combinatorial bases of polynomials, defined by positive expansions. These bases include the well-studied Schubert polynomials, Demazure characters and Demazure atoms, as well as the recently-introduced slide and quasi-key bases. The product of a Schur polynomial and an element of a basis in the poset expands positively in that basis; in particular we give the first Littlewood-Richardson rule for the product of a Schur polynomial and a quasi-key polynomial, extending the rule of Haglund, Luoto, Mason and van Willigenburg for quasi-Schur polynomials. We also establish a bijection connecting the combinatorial models of semi-skyline fillings and quasi-key tableaux for these polynomials.}

%% 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{Schur polynomials, Demazure atoms, quasi-key polynomials, slide polynomials}

%% 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{53-Searles.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}

The ring of polynomials in $n$ variables possesses several bases that have important applications to geometry and representation theory. Principal examples include the Schubert polynomials $\sch_w$ \cite{LS82} and Demazure characters $\key_{\bf a}$ \cite{Dem74}. Other bases such as the Demazure atoms $\atom_{\bf a}$ \cite{LS90}, the fundamental and monomial slide polynomials $\Fund_{\bf a}$, $\Mono_{\bf a}$ \cite{AS1}, and the quasi-key polynomials $\qkey_{\bf a}$ \cite{AS2} have been introduced and used to study these bases from a combinatorial perspective. Here we seek to unify the various approaches and models; we begin by establishing a poset structure on these bases, defined by positive expansions.



%Finally, we compare the combinatorial tableau models developed for the monomial expansions of quasi-key polynomials and Demazure atoms. We provide a bijection between these models



\begin{figure}[ht]
\[
\begin{tikzcd}
\sch_w \arrow[rr] & & \key_{\bf a} \arrow[rr] & & \qkey_{\bf a}  \arrow[rr] \arrow[d] & & \Fund_{\bf a}  \arrow[rr] \arrow[d] & & \Mono_{\bf a} \arrow[d] &  \\
& & & & \atom_{\bf a}  \arrow [rr] & & \Part_{\bf a} \arrow[rr] & & x^{\bf a}  &
\end{tikzcd}
\]
  \caption{\label{fig:expand}The positivity poset $\mathcal{P}$ on combinatorial bases of polynomials.}
\end{figure}



\begin{theorem}[\cite{Searles17}]\label{thm:positivity}
Given the poset $\mathcal{P}$ on polynomial bases whose Hasse diagram is shown in Figure~\ref{fig:expand}, for $\mathcal{B}$ a basis in $\mathcal{P}$, all $f\in \mathcal{B}$ expand positively in $\mathcal{B}'\in \mathcal{P}$ if and only if $\mathcal{B} > \mathcal{B}'$ in $\mathcal{P}$. 
\end{theorem}

Positivity of the expansion of Schubert polynomials into Demazure characters was proved by Lascoux and Sch\"utzenberger \cite{LS90} and Reiner and Shimozono \cite{RS95}. Positivity of the expansion of Demazure characters into Demazure atoms was proved in \cite{LS90} and also by Mason in \cite{Mason08}. Positivity of the other expansions in the top row of Figure~\ref{fig:expand} were proved by Assaf and the author \cite{AS1}, \cite{AS2}. 
We give positive combinatorial formulas establishing the remaining positivity relationships in $\mathcal{P}$.


For several of the bases in $\mathcal{P}$, a positivity condition on multiplication by elements of the important Schur basis $s_\lambda$ of symmetric polynomials had been observed or proven. We complete this picture by proving that every basis in $\mathcal{P}$ satisfies this positivity statement. In particular it holds for the quasi-key polynomials, and for a new basis of polynomials we call fundamental particles $\Part_{\bf a}$ which provides a simultaneous refinement of Demazure atoms and fundamental slide polynomials.


%moreover we show that every basis $\mathcal{B}\in \mathcal{P}$ satisfies a positivity property for multiplication with Schur polynomials $s_\lambda$:

\begin{theorem}[\cite{Searles17}]\label{thm:LR}
For any polynomial basis $\mathcal{B}$ in the poset $\mathcal{P}$, any weak composition ${\bf a}$ of length $n$ and $f_{\bf a}\in \mathcal{B}$ the polynomial indexed by ${\bf a}$, the product 
\[f_{\bf a} \cdot s_{\lambda}(x_1,\ldots x_n)\] 
expands positively in the basis $\mathcal{B}$.
\end{theorem}

For Schubert polynomials, this statement is clear from the associated
geometry: the structure constants are counting points in the intersection
of three Schubert subvarieties in general position, one for a
Grassmannian variety and two for the complete flag variety. For
fundamental and monomial slide polynomials (also ordinary monomials,
trivially) this statement is clear from the fact these bases have
positive structure constants and the fact that Schur polynomials expand
positively in these bases, proved in \cite{AS1}. The other four bases do
not have positive structure constants. For Demazure characters and
Demazure atoms, Haglund, Luoto, Mason and van Willigenburg gave
Littlewood--Richardson rules for products with Schur polynomials in
\cite{HLMvW11b}. We give Littlewood--Richardson rules for products with Schur polynomials for the two remaining bases: the quasi-key polynomials and the fundamental particles.


In \cite{AS2}, quasi-key polynomials are defined combinatorially in terms of \emph{quasi-Kohnert} (or \emph{quasi-key}) tableaux, based on an algorithm of Kohnert \cite{Koh91} whereas in \cite{Mason08}, Demazure atoms are defined combinatorially in terms of \emph{semi-skyline fillings} \cite{Mason08}. These two tableau models are both defined on the skyline diagram of a weak composition, but have quite different rules for the fillings allowed. We give a bijection between semi-skyline fillings and quasi-key tableaux with fixed first column, passing through reverse semistandard Young tableaux. As a consequence, we show that quasi-key tableaux and semi-skyline fillings are constructed by decomposing reverse semistandard Young tableaux into sets of runs in an essentially dual manner: the former selecting increasing runs right-to-left, and the latter selecting decreasing runs left-to-right. 











%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Definitions}\label{sec:definitions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We review bases in $\mathcal{P}$ and some of their combinatorial models. A \emph{weak composition} ${\bf a}$ is a sequence of nonnegative integers. The \emph{skyline diagram} $D({\bf a})$ of a weak composition ${\bf a}$ is the diagram with ${\bf a}_i$ boxes in row $i$, left-justified. A \emph{triple} of a skyline diagram is a collection of three boxes with two adjacent in a row and either (Type A) the third box above the right box and the lower row weakly longer, or (Type B) the third box below the left box and the higher row strictly longer. 

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{l}
        \tableau{ & \beta } \\[-0.5\cellsize]  \hspace{1.5\cellsize} \vdots  \hspace{0.4\cellsize} \\ \tableau{  \gamma & \alpha } \\  \mbox{Type A} \\ \hspace{-3\cellsize} \mbox{lower row weakly longer}
    \end{array}
    \hspace{3\cellsize}
    \begin{array}{l}
   \hspace{3\cellsize}   \tableau{ \gamma & \alpha } \\[-0.5\cellsize] \hspace{3\cellsize}  \vdots \hspace{1.5\cellsize} \\ \hspace{3\cellsize} \tableau{ \beta & } \\ \hspace{3\cellsize}\mbox{Type B} \\  \mbox{higher row strictly longer}
    \end{array}
  \end{displaymath}
  \caption{\label{fig:triple}Triples for skyline diagrams.}
\end{figure}

Given a filling of the skyline diagram, a triple (of either type) is called an \emph{inversion triple} if either $\beta>\gamma\ge \alpha$ or $\gamma \ge \alpha > \beta$, and a \emph{coinversion triple} if $\gamma \ge \beta\ge \alpha$. 

A \emph{semi-skyline filling} of the skyline diagram $D({\bf a})$ is a filling of the boxes of $D({\bf a})$ with positive integers, one per box, such that the filling weakly decreases along rows, has no repeated entries in any column, and all triples are inversion triples \cite{Mason08}. Let $\ASSF({\bf a})$ denote the semi-skyline fillings of $D({\bf a})$ whose first column entries are equal to their row index. For $S\in \ASSF({\bf a})$, let $\wt(S)$ be the weak composition whose $i$th entry is the number of occurrences of $i$ in $S$. Finally, let $x^{\bf b}$ denote the monomial $x_1^{{\bf b}_1} \cdots x_n^{{\bf b}_n}$.


\begin{theorem}[\cite{Mason08}]\label{thm:atomSSAF}
\[\atom_{\bf a} = \sum_{S\in \ASSF({\bf a})}x^{\wt(S)}.\]
\end{theorem} 

For example, $\atom_{103} = x^{103} + x^{112} +x^{202} + x^{121} +x^{211}$, which is computed by the elements of $\ASSF(103)$ shown in Figure~\ref{fig:atom103} below.


\begin{figure}[ht]
  \begin{center}
    \begin{displaymath}
      \begin{array}{c@{\hskip2\cellsize}c@{\hskip2\cellsize}c@{\hskip2\cellsize}c@{\hskip2\cellsize}c}
        \vline\tableau{  3 & 3 & 3 \\ \\  1  \\\hline } &
        \vline\tableau{ 3 & 3 & 2 \\ \\  1  \\\hline } &
        \vline\tableau{  3 & 3 & 1 \\ \\  1  \\\hline } &
        \vline\tableau{  3 & 2 & 2 \\ \\  1  \\\hline } &
        \vline\tableau{  3 & 2 & 1 \\ \\  1  \\\hline } 
      \end{array}
    \end{displaymath}
    \caption{\label{fig:atom103}The five elements of $\ASSF(103)$.}
  \end{center}
\end{figure}


In \cite{Dem74}, Demazure introduced the basis of \emph{Demazure characters}, also known as \emph{key polynomials}. There are many different combinatorial formulas for computing the monomial expansion of a Demazure character \cite{RS95}; here we express a Demazure character as a sum of Demazure atoms. 

\begin{definition}[\cite{AS2}]\label{def:lswap}
Given a weak composition ${\bf a}$, let a \emph{left swap} be the exchange of two parts ${\bf a}_i \le {\bf a}_j$ where $i<j$. Let $\lswap({\bf a})$ be the set of weak compositions ${\bf b}$ that can be obtained from ${\bf a}$ by a (possibly empty) sequence of left swaps starting with ${\bf a}$. %Let $\Qlswap(a)$ be all $b\in \lswap(a)$ such that if $c\in \lswap(a)$ and $\flatten(b) = \flatten(c)$, then $c \ge b$. 
\end{definition}

For example, $\lswap(1,0,3) = \{(1,0,3), (1,3,0), (3,0,1), (3,1,0)\}.$


\begin{lemma}[\cite{Searles17}]\label{lem:lswap}
The Demazure atom expansion of a Demazure character is given by
\[\key_{\bf a} = \sum_{{\bf b}\in \lswap({\bf a})} \atom_{\bf b}.\]
\end{lemma}

For example, $\key_{103} = \atom_{103} +  \atom_{130}  + \atom_{301} + \atom_{310}.$

Lemma~\ref{lem:lswap} is a rephrasing of a Bruhat order condition on permutations (see, e.g., \cite{Mason}, \cite{HLMvW11b}) in terms of weak compositions.


In \cite{AS1}, Assaf and the author define \emph{monomial} and \emph{fundamental slide polynomials}, polynomial ring analogues of the monomial and fundamental bases of quasisymmetric polynomials \cite{Ges84}. Given a weak composition ${\bf a}$, let $\flatten({\bf a})$ be the (strong) composition obtained by removing all $0$ terms from ${\bf a}$; for example, $\flatten(0,2,3,0,1) = (2,3,1)$. Given weak compositions ${\bf a},{\bf b}$ of length $n$, we say ${\bf b}$ \emph{dominates} ${\bf a}$, denoted by ${\bf b} \geq {\bf a}$, if $ {\bf b}_1 + \cdots + {\bf b}_i \geq {\bf a}_1 + \cdots + {\bf a}_i$  for all $1\le i\le n$. 

\begin{definition}[\cite{AS1}]
  Given a weak composition ${\bf a}$, the \emph{monomial slide polynomial} $\Mono_{{\bf a}}$ and \emph{fundamental slide polynomial} $\Fund_{\bf a}$ are defined by
    \[\Mono_{\bf a} = \sum_{\substack{{\bf b} \geq {\bf a} \\ \flatten({\bf b}) = \flatten({\bf a})}} x^{\bf b} \qquad \mbox{ and } \qquad \Fund_{\bf a} = \sum_{\substack{{\bf b} \geq {\bf a} \\ \flatten({\bf b}) \ \mathrm{refines} \ \flatten({\bf a})}} x^{\bf b}. \]
\end{definition}

For example,  $\Mono_{103} = x^{103} +  x^{130}$ and $\Fund_{103} = x^{103} + x^{130} + x^{112} + x^{121}.$



\begin{definition}[\cite{AS2, Searles17}]\label{def:qktableaux}
Given a weak composition ${\bf a}$, a \emph{quasi-key tableau of shape ${\bf a}$} is a filling of $D({\bf a})$ with positive integers satisfying
\begin{enumerate}
\item entries weakly decrease along rows, and no entry of row $i$ exceeds $i$
\item entries in any column are distinct, and entries increase up the first column
\item if an entry $i$ is above an entry $k$ in the same column with $i<k$, then there is a label $j$ immediately right of $k$, with $i<j$
\item Given two rows with the higher row strictly longer, then if entry $i$ is in column $c$ of the lower row and entry $j$ in column $c+1$ of the higher row, then  $i<j$.
\end{enumerate}
Denote the set of quasi-key tableaux of shape ${\bf a}$ by $\qKT({\bf a})$; for example, see Figure~\ref{fig:qKey032}.  Let $\qKT^{(1)}({\bf a})$ be those elements of $\qKT({\bf a})$ whose first column entries are equal to their row index; for example, the first five tableaux in Figure~\ref{fig:qKey032}.
\end{definition}




\begin{figure}[ht]
  \begin{center}
    \begin{displaymath}
      \begin{array}{c@{\hskip2\cellsize}c@{\hskip2\cellsize}c@{\hskip2\cellsize}c@{\hskip2\cellsize}c@{\hskip2\cellsize}c@{\hskip2\cellsize}c@{\hskip2\cellsize}c}
        \vline\tableau{  3 & 3  \\   2 & 2 & 2 \\ \\\hline } &
        \vline\tableau{  3 & 3  \\   2 & 2 & 1 \\ \\\hline } &
        \vline\tableau{  3 & 3  \\   2 & 1 & 1 \\ \\\hline } &
        \vline\tableau{  3 & 2  \\   2 & 1 & 1 \\ \\\hline } &
        \vline\tableau{  3 & 1  \\   2 & 2 & 2 \\ \\\hline } &
        \vline\tableau{  3 & 3  \\   1 & 1 & 1 \\ \\\hline } &
        \vline\tableau{  3 & 2  \\   1 & 1 & 1 \\ \\\hline } &
        \vline\tableau{  2 & 2  \\   1 & 1 & 1 \\ \\\hline } 
      \end{array}
    \end{displaymath}
    \caption{\label{fig:qKey032}The 8 elements of $\qKT(032)$.}
  \end{center}
\end{figure}


\begin{definition}[\cite{AS2, Searles17}]\label{def:qkey}
  Given a weak composition ${\bf a}$, the \emph{quasi-key polynomial} $\qkey_{\bf a}$ and the \emph{column quasi-key polynomial} $\qkey^{(1)}_{\bf a}$ are defined by
  \begin{equation}\nonumber
    \qkey_{\bf a} = \sum_{T \in \qKT({\bf a})} x^{\wt(T)} \qquad \mbox{ and } \qquad  \qkey^{(1)}_{\bf a} = \sum_{T \in \qKT^{(1)}({\bf a})} x^{\wt(T)}.
  \end{equation}
  \label{def:quasi-key}
\end{definition}
For example, we compute $\qkey_{032}  =  x^{032} + x^{122} + x^{212} + x^{221} + x^{131} + x^{302} + x^{311} + x^{320}$ from Figure~\ref{fig:qKey032}, and $\qkey^{(1)}_{032}  =  x^{032} + x^{122} + x^{212} + x^{221} + x^{131}$ from the first five tableaux in Figure~\ref{fig:qKey032}.

%\begin{definition}(\cite{AS2, Searles17})\label{def:qkey}
%  Given a weak composition $a$, the \emph{quasi-key polynomial} $\qkey_a$ is defined by
%  \begin{equation}\nonumber
 %   \qkey_a = \sum_{T \in \qKT(a)} x^{\wt(T)}.
 % \end{equation}
 % \label{def:quasi-key}
%\end{definition}
%For example, we compute $\qkey_{032}  =  x^{032} + x^{122} + x^{212} + x^{221} + x^{131} + x^{302} + x^{311} + x^{320}$ from Figure~\ref{fig:qKey032}.

%\begin{definition}(\cite{Searles17})\label{def:qkey1}
 % For a weak composition $a$, the \emph{column quasi-key polynomial} $\qkey^{(1)}_a$ is given by
 % \begin{equation}\nonumber
  %  \qkey^{(1)}_a = \sum_{T \in \qKT^{(1)}(a)} x^{\wt(T)}.
 % \end{equation}
 % \label{def:quasi-key1}
%\end{definition}

%For example, we compute $\qkey^{(1)}_{032}  =  x^{032} + x^{122} + x^{212} + x^{221} + x^{131}$ from the first five tableaux in Figure~\ref{fig:qKey032}.

%The quasi-key polynomials expand positively in the fundamental slide basis. %The following are direct translations of \cite{AS2} from the language of quasi-Kohnert tableaux to the language of quasi-key tableaux (see Remark~\ref{rmk:quasi-key}).

\begin{definition}[\cite{AS2}]\label{def:quasi-Yamanouchi}
  A quasi-key tableau is \emph{quasi-Yamanouchi} if the leftmost occurrence of each entry $i$ is either in row $i$, or weakly left of some entry $i+1$. Denote the set of quasi-Yamanouchi quasi-key tableaux of shape ${\bf a}$ by $\QqKT({\bf a})$.
  \label{def:quasi-Yam}
\end{definition}

The quasi-Yamanouchi quasi-key tableaux index the fundamental slide expansion of a quasi-key polynomial.

\begin{theorem}[\cite{AS2}]
  For a weak composition ${\bf a}$, we have
    \[\qkey_{\bf a} = \sum_{T \in \QqKT({\bf a})} \Fund_{\wt(T)}.\]
\end{theorem}

For example, the first, fourth and fifth quasi-Kohnert tableaux in Figure~\ref{fig:qKey032} are quasi-Yamanouchi. Therefore $\qkey_{032} = \Fund_{032} + \Fund_{221} + \Fund_{131}.$

Let $\Qlswap({\bf a})$ be the set containing all ${\bf b}\in \lswap({\bf a})$ such that if ${\bf c}\in \lswap({\bf a})$ and $\flatten({\bf b}) = \flatten({\bf c})$, then ${\bf c} \ge {\bf b}$. 
For example, $\Qlswap(1,0,3) = \{(1,0,3), (3,0,1)\}.$

Then the expansion of a Demazure character into the quasi-key basis is given by

\begin{theorem}[\cite{AS2}]\label{thm:keytoqkey}
\[\key_{\bf a} = \sum_{{\bf b}\in \Qlswap({\bf a})} \qkey_{\bf b}.\]
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{A Littlewood--Richardson rule for quasi-keys}\label{sec:LR}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Demazure atom expansion}

We first establish an explicit positive formula for the Demazure atom expansion of a quasi-key polynomial. 

\begin{theorem}[\cite{Searles17}]\label{thm:atomexpansion}
Given a weak composition ${\bf a}$, the Demazure atom expansion of the quasi-key polynomial $\qkey_{\bf a}$ is given by 
\[\qkey_{\bf a} = \sum_{\stackrel{{\bf b}\ge {\bf a}}{\flatten({\bf b})=\flatten({\bf a})}}\atom_{\bf b}.\]
\end{theorem}

The quasi-key basis contains the \emph{quasi-Schur} basis of quasisymmetric polynomials introduced by Haglund, Luoto, Mason and van Willigenburg in \cite{HLMvW11a}. From Theorem~\ref{thm:atomexpansion} we recover the Demazure atom expansion of a quasi-Schur polynomial:

\begin{corollary}[\cite{HLMvW11a}] Let $\alpha$ be a strong composition. The Demazure atom expansion of the quasi-Schur polynomial $QS_\alpha(x_1,\ldots , x_n)$ is given by
\[QS_\alpha(x_1,\ldots , x_n) = \sum_{\flatten({\bf b})=\alpha}\atom_{\bf b},\]
where ${\bf b}$ is a weak composition of length $n$.
\end{corollary}

The column quasi-key polynomials (Definition~\ref{def:qkey}) are precisely the Demazure atoms.

\begin{theorem}[\cite{Searles17}]
For any weak composition ${\bf a}$, we have $\atom_{\bf a} = \qkey^{(1)}_{\bf a}$.
\end{theorem}


As a result, Demazure atoms may expressed in terms of quasi-key tableaux. Similarly, quasi-key polynomials may be expressed in terms of semi-skyline fillings. Let $\SSF({\bf a})$ be the set of all semi-skyline fillings of $D({\bf a})$ such that entries in the first column do not exceed their row index.

\begin{corollary}
\[\qkey_{\bf a} = \sum_{S\in \SSF({\bf a})} x^{\wt(S)}.\]
%where the sum is over semi-skyline fillings of $D({\bf a})$ such that entries in the first column of $S$ do not exceed their row index.
\end{corollary}

In Section~\ref{sec:bijection} we will establish an explicit bijection between these models.









\subsection{Littlewood--Richardson rule}

We now give a positive combinatorial formula for the expansion of the product of a quasi-key polynomial and a Schur polynomial in the quasi-key basis.

We recall the definition of \emph{Littlewood--Richardson skew skyline tableaux} ($\LRS$) from \cite{HLMvW11b}. Let ${\bf a}$ and ${\bf b}$ be weak compositions of length $n$ with ${\bf a}_i\le {\bf b}_i$ for all $i$. Then an $\LRS$ of shape ${\bf b}/{\bf a}$ is a filling of $D({\bf b})$ such that both the \emph{basement} (an additional ``0th'' column) and the boxes of $D({\bf a})\subseteq D({\bf b})$ are filled with asterisks ``$\ast$'' and the remaining boxes are filled with positive integers such that the filling weakly decreases along rows, does not repeat an entry in any column, and all triples (including those involving basement entries) are inversion triples.  (To determine the status of a triple involving $\ast$ symbols, following \cite{HLMvW11b} we say that $\ast=\infty$, $\ast$ symbols in the same row are equal, and $\ast$ symbols in the same column increase from top to bottom.) For an example, see Figure~\ref{fig:swap}.

%For example, see Figure~\ref{fig:LRS0103}.
\excise{
\begin{figure}[ht]
\begin{center}
\begin{picture}(192,48)

\put(3.5,3.5){$\ast$}
\put(3.5,15.5){$\ast$}
\put(3.5,27.5){$\ast$}
\put(3.5,39.5){$\ast$}

\put(15.5,15.5){$\ast$}
\put(27.5,15.5){$2$}

\put(15.5,26.5){$1$}

\put(15.5,39.5){$\ast$}
\put(27.5,39.5){$\ast$}
\put(39.5,39.5){$\ast$}
\put(51.5,38.5){$2$}




\put(12,0){\line(1,0){48}}
\put(12,0){\line(0,1){48}}


\put(12,12){\line(1,0){24}}
\put(12,24){\line(1,0){24}}
\put(12,36){\line(1,0){48}}
\put(12,48){\line(1,0){48}}

\put(24,12){\line(0,1){36}}
\put(36,12){\line(0,1){12}}
\put(36,36){\line(0,1){12}}
\put(48,36){\line(0,1){12}}
\put(60,36){\line(0,1){12}}

%ends at 72 units across

%second picture

%start at 120 units across


\put(123.5,3.5){$\ast$}
\put(123.5,15.5){$\ast$}
\put(123.5,27.5){$\ast$}
\put(123.5,39.5){$\ast$}

\put(135.5,15.5){$\ast$}
\put(147.5,15.5){$1$}

\put(135.5,26.5){$2$}

\put(135.5,39.5){$\ast$}
\put(147.5,39.5){$\ast$}
\put(159.5,39.5){$\ast$}
\put(171.5,38.5){$2$}




\put(132,0){\line(1,0){48}}
\put(132,0){\line(0,1){48}}


\put(132,12){\line(1,0){24}}
\put(132,24){\line(1,0){24}}
\put(132,36){\line(1,0){48}}
\put(132,48){\line(1,0){48}}

\put(144,12){\line(0,1){36}}
\put(156,12){\line(0,1){12}}
\put(156,36){\line(0,1){12}}
\put(168,36){\line(0,1){12}}
\put(180,36){\line(0,1){12}}



\end{picture}
\caption{\label{fig:LRS0103}Two $\LRS$ of shape $(0,2,1,4)/(0,1,0,3)$.}
\end{center}
\end{figure}
}

%\begin{picture}(0,0)
%\put(155,56){$\ast$}
%\end{picture}

Given an $\LRS$ $L$, form the \emph{column word} of $L$ by reading entries of $L$ from bottom to top in each column, beginning with the rightmost column and working leftwards, ignoring asterisks. A column word whose largest letter is $k$ is called \emph{contre-lattice} if for all $i$, the subword consisting of the first $i$ letters has at least as many $k$'s as $k-1$'s, at least as many $k-1$'s as $k-2$'s, etc. For example, $4432314213$ is contre-lattice. Let $\lambda = \lambda_1\ge \ldots \lambda_\ell>0$ be a partition of length $\ell$ and let $\lambda^\ast$ be the multiset of numbers $1^{\lambda_\ell} 2^{\lambda_{\ell-1}} \ldots \ell^{\lambda_1}$.  

With this, Haglund, Luoto, Mason and van Willigenburg \cite{HLMvW11b}
give the following Littlewood--Richardson rule for the Demazure atom expansion of the product of a Demazure atom and a Schur polynomial. 

\begin{theorem}[\cite{HLMvW11b}]\label{thm:atomxschur}
Let ${\bf a}$ be a weak composition of length $n$ and $\lambda$ a partition. Then
\[\atom_{\bf a} \cdot s_\lambda(x_1,\ldots , x_n) = \sum_{\bf b} c_{{\bf a},\lambda}^{\bf b}\atom_{\bf b},\]
where ${\bf b}$ is a weak composition of length $n$ and $c_{{\bf a},\lambda}^{\bf b}$ is the number of $\LRS$ of shape ${\bf b}/{\bf a}$, content $\lambda^\ast$.
\end{theorem}



Let $L$ be an $\LRS$ with an occupied row $i$. If row $i+1$ is empty, let $\swap_{i, i+1}(L)$ be the diagram obtained by moving all entries of row $i$ up to row $i+1$; similarly if row $i-1$ is empty, let $\swap_{i, i-1}(L)$ be the diagram obtained by moving all entries of row $i$ down to row $i-1$. For example, see Figure~\ref{fig:swap}.




\begin{figure}[ht]
\begin{center}
\begin{picture}(288,48)

\put(3.5,3.5){$\ast$}
\put(3.5,15.5){$\ast$}
\put(3.5,27.5){$\ast$}
\put(3.5,39.5){$\ast$}

\put(15.5,14.5){$2$}
\put(27.5,14.5){$1$}

\put(15.5,3.5){$\ast$}

\put(15.5,39.5){$\ast$}
\put(27.5,39.5){$\ast$}
\put(39.5,39.5){$\ast$}
\put(51.5,38.5){$2$}




\put(12,0){\line(1,0){48}}
\put(12,0){\line(0,1){48}}


\put(12,12){\line(1,0){24}}
\put(12,24){\line(1,0){24}}
\put(12,36){\line(1,0){48}}
\put(12,48){\line(1,0){48}}

\put(24,0){\line(0,1){24}}
\put(24,36){\line(0,1){12}}

\put(36,12){\line(0,1){12}}
\put(36,36){\line(0,1){12}}
\put(48,36){\line(0,1){12}}
\put(60,36){\line(0,1){12}}

%ends at 72 units across

%second picture

%start at 108 units across
%ends at 180 units across


\put(111.5,3.5){$\ast$}
\put(111.5,15.5){$\ast$}
\put(111.5,27.5){$\ast$}
\put(111.5,39.5){$\ast$}

\put(123.5,26.5){$2$}
\put(135.5,26.5){$1$}

\put(123.5,3.5){$\ast$}

\put(123.5,39.5){$\ast$}
\put(135.5,39.5){$\ast$}
\put(147.5,39.5){$\ast$}
\put(159.5,38.5){$2$}




\put(120,0){\line(1,0){48}}
\put(120,0){\line(0,1){48}}


\put(120,12){\line(1,0){12}}
\put(120,24){\line(1,0){24}}
\put(120,36){\line(1,0){48}}
\put(120,48){\line(1,0){48}}

\put(132,0){\line(0,1){12}}
\put(132,24){\line(0,1){24}}
\put(144,24){\line(0,1){24}}
%\put(144,36){\line(0,1){12}}
\put(156,36){\line(0,1){12}}
\put(168,36){\line(0,1){12}}

%third picture

%starts at 216 units across
%ends at 288 units across

\put(219.5,3.5){$\ast$}
\put(219.5,15.5){$\ast$}
\put(219.5,27.5){$\ast$}
\put(219.5,39.5){$\ast$}

\put(231.5,26.5){$2$}
\put(243.5,26.5){$1$}

\put(231.5,15.5){$\ast$}

\put(231.5,39.5){$\ast$}
\put(243.5,39.5){$\ast$}
\put(255.5,39.5){$\ast$}
\put(267.5,38.5){$2$}




\put(228,0){\line(1,0){48}}
\put(228,0){\line(0,1){48}}


\put(228,12){\line(1,0){12}}
\put(228,24){\line(1,0){24}}
\put(228,36){\line(1,0){48}}
\put(228,48){\line(1,0){48}}

\put(240,12){\line(0,1){36}}
\put(252,24){\line(0,1){24}}
%\put(252,36){\line(0,1){12}}
\put(264,36){\line(0,1){12}}
\put(276,36){\line(0,1){12}}



\end{picture}
  \caption{\label{fig:swap}An $\LRS$ $L$ of shape $1204/1003$, $L'=\swap_{2,3}(L)$ and  $L''=\swap_{1,2}(L')$.}
\end{center}
\end{figure}


The lemma below is clear, but important in proving our Littlewood--Richardson rule.

\begin{lemma}[\cite{Searles17}]\label{lem:rowtranslate}
If $L$ is an $\LRS$, then $\swap_{i, i+1}(L)$ and $\swap_{i, i-1}(L)$ also satisfy the triple conditions, and have a contre-lattice column word if and only if the column word of $L$ is contre-lattice.
\end{lemma}



Given weak compositions ${\bf a}$ and ${\bf b}$ of length $n$, define $\LRS({\bf a},{\bf b})$ to be the set of $\LRS$ of shape ${\bf b}/{\bf c}$ where ${\bf c}$ is any weak composition of length $n$ satisfying ${\bf c}\ge {\bf a}$ and $\flatten({\bf c}) = \flatten({\bf a})$. Say an element $L\in \LRS({\bf a},{\bf b})$ is \emph{highest-weight} if for every row $i$ of $L$, $\swap_{i, i+1}(L)$ is not an element of $\bigcup_{\bf d} \LRS({\bf a},{\bf d})$, where ${\bf d}$ ranges over weak compositions of length $n$. Denote the set of highest-weight elements of $\LRS({\bf a},{\bf b})$ by $\HLRS({\bf a},{\bf b})$.


\begin{example} Suppose $n=4$ and ${\bf a}=(0,1,0,3)$. Then the rightmost $\LRS$ in Figure~\ref{fig:swap} is highest-weight: we would not be able to apply e.g. $\swap_{4,5}$, since the result would no longer be inside $\bigcup_{\bf d} \LRS({\bf a},{\bf d})$. The leftmost two $\LRS$ in Figure~\ref{fig:swap} are not highest-weight.
\end{example}

%We may now state our Littlewood--Richardson rule for quasi-key polynomials.

\begin{theorem}[\cite{Searles17}]
Let ${\bf a}$ be a weak composition of length $n$ and $\lambda$ a partition. Then
\[\qkey_{\bf a}\cdot s_\lambda(x_1,\ldots , x_n) = \sum_{\bf b} C_{{\bf a},\lambda}^{\bf b}\qkey_{\bf b},\]
where ${\bf b}$ is a weak composition of length $n$, $C_{{\bf a},\lambda}^{\bf b}$ is the number of $\HLRS({\bf a},{\bf b})$ with content $\lambda^\ast$.
\end{theorem}

%\begin{proof}
%By Theorem~\ref{thm:atomexpansion}, the left-hand side is equal to 
%\[\sum_{\substack{c\ge a \\ \flatten(c)=\flatten(a)}}\atom_c\cdot s_\lambda(x_1,\ldots x_n).\]

%By Theorem~\ref{thm:atomxschur}, the Demazure atom expansion of this expression is indexed by the elements of $\bigcup_d \LRS(a,d)$ (where $d$ ranges over weak compositions of length $n$) with content $\lambda^\ast$ and contre-lattice column word. We need to collect these Demazure atoms into quasi-key polynomials.

%Let $L\in \bigcup_d \LRS(a,d)$ be an $\LRS$ indexing a Demazure atom appearing in the expansion of the left hand side. Consider the closure of the action of the operators $\swap_{i,i+1}$ and $\swap_{i,i-1}$ on $L$, with the restriction that these operators may be applied only if the image remains in $\bigcup_d \LRS(a,d)$. By Lemma~\ref{lem:rowtranslate}, everything thus obtained is an element of $\bigcup_d \LRS(a,d)$ with content $\lambda^\ast$ and contre-lattice column word, hence indexes an atom in the expansion of the the left-hand side. Since the swap operators do not change the rows of an $\LRS$, but only move them up and down, this action of the swap operators partitions $\bigcup_d \LRS(a,d)$ into equivalence classes.

%Consider such an equivalence class. The $\LRS$ whose underlying composition is smallest in dominance order (say $b$) in this class is by definition an element of $\HLRS(a,b)$, and each element of $\HLRS(a,b)$ belongs to exactly one equivalence class. Moreover, by the definition of the swap operators, the underlying weak compositions of the elements of an equivalence class are exactly those $b'$ satisfying $b'\ge b$ and $\flatten(b')=\flatten(b)$. Hence the sum of all atoms in the class is $\qkey_b$.
%\end{proof}









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{The fundamental particle basis of polynomials}\label{sec:particle}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Completing the picture of $\mathcal{P}$, we introduce the \emph{fundamental particle} basis $\{\Part_{\bf a}\}$ of the polynomial ring. This basis is a common refinement of both fundamental slide polynomials and Demazure atoms.


Define the \emph{fixed slides} of ${\bf a}$ to be those weak compositions obtainable from ${\bf a}$ by performing a series of local moves of the form $0k \rightarrow ij$, where $i,j \ge 0$, $i+j=k$, and if $k$ occupies a position that is nonzero in ${\bf a}$, then $j>0$. Let $\FS({\bf a})$ denote the set of all fixed slides of ${\bf a}$.


\begin{definition}[\cite{Searles17}]
Given a weak composition ${\bf a}$, the fundamental particle $\Part_{\bf a}$ is given by
\[\Part_{\bf a} = \sum_{{\bf b}\in\FS({\bf a})}x^{\bf b}.\]
\end{definition}




For example, $\Part_{0302} = x^{0302} + x^{1202} + x^{2102} + x^{0311} + x^{1211} + x^{2111}.$

\begin{proposition}[\cite{Searles17}]
$\{\Part_{\bf a}\}$ is a basis for the polynomial ring.
\end{proposition}
%\begin{proof}
%The leading monomial of $\Part_a$ with respect to dominance order is $x^a$, so we have a triangularity with the basis of (ordinary) monomials.
%\end{proof}

%\subsection{Positivity}

Fundamental slide polynomials expand positively in fundamental particles:

\begin{proposition}[\cite{Searles17}]\label{prop:fundtoparticle}
\[\Fund_{\bf a} = \sum_{\stackrel{{\bf b}\ge {\bf a}}{\flatten({\bf b})=\flatten({\bf a})}}\Part_{\bf b}.\]
\end{proposition}


For example, $\Fund_{0302} = \Part_{0302} + \Part_{3002} + \Part_{0320} + \Part_{3020} + \Part_{3200}.$



\begin{remark}
This formula is the same as that for the expansion of quasi-key polynomials in Demazure atoms and monomial slide polynomials in ordinary monomials; all downward arrows in Figure~\ref{fig:expand} have the same formula.
\end{remark}

Demazure atoms also expand positively into fundamental particles. Say $S\in \ASSF({\bf a})$ is \emph{particle-highest} if for every $i$ that appears as an entry in $S$, either the leftmost $i$ is in the first column or there is an $i^\uparrow$ in some column weakly to its right, where $i^\uparrow$ is the smallest label greater than $i$ appearing in $S$. Let $\HSSF({\bf a})$ denote the set of particle-highest elements of $\ASSF({\bf a})$.

\begin{example}\label{ex:HSSF}
Only the first and third $\ASSF$s in Figure~\ref{fig:atom103} are in $\HSSF(1,0,3)$.
\end{example}

To give a formula for the fundamental particle expansion of a Demazure atom, we define a \emph{destandardization} operation $\destand$ on $\ASSF({\bf a})$. For each $i$ appearing in $S\in \ASSF({\bf a})$, if the leftmost $i$ is not in the first column, and has no $i^\uparrow$ weakly to its right, then replace every $i$ in $S$ with $i+1$. Repeat until no further changes can be made: the result is $\destand(S)$. 

\begin{lemma}[\cite{Searles17}]\label{lem:dst}
If $S\in \ASSF({\bf a})$ then $\destand(S)\in \HSSF({\bf a})$, and $\destand(S)=S$ if and only if $S\in \HSSF({\bf a})$. 
\end{lemma}

\begin{example}
In Figure~\ref{fig:atomdst}, the leftmost $\ASSF$ is not particle-highest and destandardizes to the particle-highest $\ASSF$ in the middle, while the rightmost $\ASSF$ is particle-highest (and destandardizes to itself).
\end{example}


\begin{figure}[ht]
  \begin{center}
    \begin{displaymath}
      \begin{array}{c@{\hskip 2\cellsize}c@{\hskip 4\cellsize}c}
        \vline\tableau{ 5 & 1 \\ \\ 3 & 2 \\ \\ \\ \hline } \,\,\,\,\,\,\,\,\,\,\,\,\, \substack{dst \\ \longrightarrow} \,\,\,\, &
        \vline\tableau{ 5 & 1 \\ \\ 3 & 3  \\ \\ \\ \hline } \qquad \qquad &
        \vline\tableau{ 5 & 2 \\ \\ 3 & 3 \\ \\ \\ \hline } 
      \end{array}
    \end{displaymath}
    \caption{\label{fig:atomdst} Three elements of $\ASSF(00202)$. The rightmost two are also elements of $\HSSF(00202)$.}
  \end{center}
\end{figure}

\begin{theorem}[\cite{Searles17}]\label{thm:atomtoparticle}
Let ${\bf a}$ be a weak composition of length $n$. Then
\[\atom_{\bf a} = \sum_{S\in \HSSF({\bf a})}\Part_{\wt(S)}.\]
\end{theorem}

For example, from Example~\ref{ex:HSSF} we have $\atom_{103} = \Part_{103} + \Part_{202}.$






%\subsection{Littlewood--Richardson rule}

Like the Demazure atom basis, the fundamental particle basis does not have positive structure constants. However, the product of a fundamental particle and a Schur polynomial does expand positively in the basis of fundamental particles. 

Let ${\bf a}$ be a weak composition of length $n$ and let $\revSSYT_n$ denote the set of reverse semistandard Young tableaux of shape $\lambda$ whose largest entry is at most $n$. By definition, the monomials appearing in the product $\Part_{\bf a}\cdot s_\lambda(x_1,\ldots , x_n)$ arise from the pairs $(S,T)$ where $S \in \LSSF({\bf a})$, $T\in \revSSYT_n(\lambda)$. Denote the set of such pairs by $\Pairs({\bf a}, \lambda)$, and for $(S,T)\in \Pairs({\bf a},\lambda)$, let $\wt(S,T) = \wt(S)+\wt(T)$.
 We extend the definition of destandardization to $\Pairs({\bf a}, \lambda)$ by considering every label in $T$ to be strictly right of every label in $S$ when applying $\destand$ to $(S,T)\in \Pairs({\bf a}, \lambda)$. Let $\HPairs({\bf a},\lambda)$ be the set $\{\destand(S,T) : (S,T) \in \Pairs({\bf a},\lambda)\}$. For an example, see Figure~\ref{fig:pairs}. 


\begin{figure}[ht]
  \begin{center}
    \begin{displaymath}
      \begin{array}{cc@{\hskip\cellsize}cc}
        \vline\tableau{ 4 & 3 \\ \\ 2 & 1 & 1 \\ \\ \hline } & \,\,\,\,\,\,\,\,
        \tableau{ 3 & 3  \\  2 \\  \\ \\  }  \qquad \substack{dst \\ \longrightarrow} \qquad \qquad &
        \vline\tableau{ 4 & 4 \\ \\ 2 & 1 & 1 \\ \\ \hline } & \,\,\,\,\,\,\,\,
         \tableau{ 4 & 4  \\  2 \\  \\  \\ }  
      \end{array}
    \end{displaymath}
    \caption{\label{fig:pairs} Destandardization of an element of $\Pairs((0,3,0,2),(2,1))$, where $n=4$.}
  \end{center}
\end{figure}


\begin{lemma}[\cite{Searles17}]\label{lem:destandpairs}
If $(S,T)\in \Pairs({\bf a},\lambda)$, then $\destand(S,T)\in \Pairs({\bf a},\lambda)$, and $\destand(S,T)=(S,T)$ if and only if $(S,T)\in \HPairs({\bf a},\lambda)$.
\end{lemma} 


\begin{theorem}[\cite{Searles17}]
Let ${\bf a}$ be a weak composition of length $n$ and $\lambda$ a partition. Then
\[\Part_{\bf a}\cdot s_\lambda(x_1,\ldots , x_n) = \sum_{(S,T)\in \HPairs({\bf a}, \lambda)}\Part_{\wt(S,T)}.\]
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{A bijection between combinatorial models}\label{sec:bijection}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\Dominic{Following on from the fact that quasi-key polynomials can be expressed in terms of either ASSFs or qKT...}
We establish a bijection between semi-skyline fillings and quasi-key tableaux. Let $\ASSF$ denote the set of all $\ASSF({\bf a})$ as ${\bf a}$ ranges over weak compositions, and define $\qKT^{(1)}$ similarly. Let $\revSSYT$ denote the set of all reverse semistandard Young tableaux of all shapes. Let the $i$'th \emph{column set} $C_i$ denote the set of entries in the $i$'th column. We begin by constructing a column-set (and thus weight) preserving bijection between $\ASSF$ and $\qKT^{(1)}$.  




We define a map $\phi:\revSSYT\rightarrow \ASSF$ that we call \emph{left row-filling}. Given $V\in \revSSYT$, form the lowest row $\phi(V)$ by first taking the smallest entry, say $i$, in the first column of $V$ and placing it in row $i$. Then fill out this row by choosing the largest entry from column $2$ of $V$ that is weakly smaller than $i$, the largest entry from column $3$ of $V$ that is weakly smaller than the entry chosen from column $2$, etc. Delete all chosen entries from $V$, then repeat the algorithm to make the second-lowest row of $\phi(V)$, etc. See Figure~\ref{fig:leftright} for an example.

\begin{remark}
The map $\phi$ preserves column sets, and agrees with Mason's bijection \cite{Mason08} between $\revSSYT$ and $\ASSF$, which is expressed in terms of filling columns rather than rows.
\end{remark}






We define a map $\psi: \revSSYT\rightarrow \qKT^{(1)}$ that we call \emph{right row-filling}. Given $V\in \revSSYT$, we build a filling $\psi(V)$ by rows. Starting with the rightmost column set, say $C_k$, of $V$, choose the smallest number in $C_k$. Then choose the smallest number in $C_{k-1}$ that is weakly larger than $k$. Continue in this manner until you end by choosing a number $\ell$ in $C_1$. The elements chosen form a row of $\psi(V)$ with row index $\ell$. Then delete all chosen elements from $V$ and repeat.  See Figure~\ref{fig:leftright} for an example.

\begin{lemma}[\cite{Searles17}]
Right row-filling is a well-defined, operation on $\revSSYT$ that preserves column sets. Moreover, for any $V\in \revSSYT$, $\psi(V)\in \qKT^{(1)}$.
\end{lemma}




\begin{figure}[ht]
  \begin{center}
    \begin{displaymath}
      \begin{array}{c@{\hskip\cellsize}c@{\hskip\cellsize}c}
        \vline\tableau{ 7 & 7 & 6 & 3 \\ 6 & 5 & 5 & 4 & 3 & 3 & 2 \\ \\  4 & 4 & 1 & 1 & 1 \\ 3 \\ 2 & 2 & 2 & 2 & 2 \\ 1 \\\hline } \,\,\,\,\,\,\, \substack{ \phi \\ \longleftarrow } \,\,\,\,\, &
        \tableau{ 7 & 7 & 6 & 4 & 3 & 3 & 2  \\  6 & 5 & 5 & 3 & 2 \\  4 & 4 & 2 & 2 & 1   \\  3 & 2 & 1 & 1 \\ 2 \\ 1  } \,\,\,\,\,\,\, \substack{\psi \\ \longrightarrow} \,\,\,\,\, &
        \vline\tableau{ 7 & 7 & 6 & 4 \\ 6 & 5 & 5 & 3 & 3 & 3 & 2 \\ \\ 4 & 4 & 2 & 2 & 2 \\ 3 \\  2 & 2 & 1 & 1 & 1 \\ 1 \\\hline } 
      \end{array}
    \end{displaymath}
    \caption{\label{fig:leftright}The left ($\phi$) and right ($\psi$) row-filling algorithms.}
  \end{center}
\end{figure}




\begin{theorem}[\cite{Searles17}]\label{thm:bijection1}
The map $\psi: \revSSYT \rightarrow \qKT^{(1)}$ is a bijection.
\end{theorem}

\begin{remark}
The inverse maps of $\phi$ and $\psi$ are given by top-justifying each tableau (to give a Young diagram), then reordering the entries in each column so they decrease from top to bottom. 
\end{remark} 

\begin{remark}
Notice the duality in the construction of $\ASSF$ and $\qKT^{(1)}$ from $\revSSYT$. The $\ASSF$ are constructed by taking minimally decreasing runs from left to right, the $\qKT^{(1)}$ by taking minimally increasing runs from right to left.
\end{remark}




\acknowledgements{The author thanks J. Haglund, S. Mason and S. van Willigenburg for helpful discussion.}


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

%\addbibresource{Bases.bib}
\printbibliography



\end{document}
