%% 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]{FPSAC2024}
\articlenumber{47}
%% 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{extarrows}
\usepackage{tikz-cd}


\theoremstyle{definition}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}

\newtheorem*{thmm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{defn}[thm]{Definition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{ex}[thm]{Example}

\def\S{\mathfrak{S}}
\def\G{\mathscr{G}}
\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\Z{\mathbb{Z}}
\def\J{\mathcal{J}}
\def\P{\mathbb{P}}
\def\N{\mathbb{N}}

\def\rothe{\operatorname{rothe}}
\def\T{\mathbb{T}}
\def\lra{\leftrightarrow}
\def\Lra{\Leftrightarrow}
\def\d{\operatorname{d}}
\def\droop{\operatorname{min-droop}}
\def\undroop{\operatorname{min-undroop}}
\def\swap{\operatorname{cross-bump-swap}}
\def\v{\mathbf{v}}
\def\i{\mathbf{i}}
\def\j{\mathbf{j}}
\def\k{\mathbf{k}}
\def\B{B}
\def\Par{\operatorname{Par}}
\def\mon{\operatorname{mon}}

\def\g{\mathfrak{g}}
\def\Tor{\operatorname{Tor}}
\def\ker{\operatorname{ker}}
\def\Inn{\operatorname{Inn}}
\def\sign{\operatorname{sign}}
\def\SSYT{\operatorname{SSYT}}
\def\SYT{\operatorname{SYT}}

\def\red{\mathsf{R}}
\def\yellow{\mathsf{L}}
\def\wt{\operatorname{wt}}


\def\End{\operatorname{End}}
\def\BPD{\operatorname{BPD}}
\def\blank{\operatorname{blank}}
\def\ker{\operatorname{ker}}
\def\Der{\operatorname{Der}}
\def\Im{\operatorname{Im}}
\def\id{\operatorname{id}}
\def\ins{S}
\def\rec{T}
\def\rowread{\operatorname{rowread}}
\def\colread{\operatorname{colread}}
\def\EG{\operatorname{EG}}
\def\shape{\operatorname{sh}}
\def\Des{\operatorname{Des}}
\def\rect{\operatorname{rect}}
\def\perm{\operatorname{perm}}
\def\jdt{\operatorname{jdt}}
\def\len{\operatorname{length}}
\def\maxcode{\operatorname{maxcode}}
\def\code{\operatorname{code}}
\def\words{\operatorname{words}}

\def\cl{\text{Cl}}
\def\ol{\overline}


\def\+{\includegraphics[scale=0.4]{cross.eps}}
\def\bl{\includegraphics[scale=0.4]{blank.eps}}
\def\bt{\includegraphics[scale=0.4]{bump.eps}}
\def\rt{\includegraphics[scale=0.4]{rtile.eps}}
\def\jt{\includegraphics[scale=0.4]{jtile.eps}}

\def\vtile{\includegraphics[scale=0.4]{vertical.eps}}
\def\htile{\includegraphics[scale=0.4]{horizontal.eps}}
\def\ch{\operatorname{ch}_{\uparrow}}
\def\chd{\operatorname{ch}_{\downarrow}}

\def\mindroop{\textsf{min-droop}}
\def\maxdroop{\textsf{max-droop}}
\def\maxd{\operatorname{max-droop}}
\def\minundroop{\textsf{min-undroop}}
\def\cbswap{\textsf{cross-bump-swap}}
\def\term{\textsf{term}}
\def\nextl{\operatorname{nextl}}
\def\recdroop{\textsf{rec-droop}}
\def\recd{\operatorname{rec-droop}}
\def\recundroop{\textsf{rec-undroop}}
\def\recund{\operatorname{rec-undroop}}
\def\uncross{\textsf{uncross}}
\def\cross{\textsf{cross}}
\def\crss{\operatorname{cross}}
\def\rect{\operatorname{rect}}
\def\pop{\operatorname{pop}}

\def\ra{\Rightarrow}


%% define your title in the usual way
\title[Growth Diagrams for Schubert RSK]{Growth Diagrams for Schubert RSK}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Daoji Huang and Son Nguyen]{Daoji Huang\thanks{\href{mailto:huan0664@umn.edu}{huan0664@umn.edu}. DH was supported by NSF Grant DMS-2202900.}\addressmark{1} \and Son Nguyen\thanks{\href{mailto:nguy4309@umn.edu}{nguy4309@umn.edu}. SN was partially supported by the University of Minnesota's Office of Undergraduate Research.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Mathematics, University of Minnesota, Minneapolis MN, 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
\abstract{Motivated by classical combinatorial Schubert calculus on the Grassmannian, Huang--Pylyavskyy introduced a generalized theory of Robinson--Schensted--Knuth (RSK) correspondence for studying Schubert calculus on the complete flag variety, via insertion algorithms. The inputs of the correspondence are certain biwords, the insertion objects are bumpless pipe dreams, and the recording objects are certain chains in Bruhat order. In particular, they defined plactic biwords and showed that classical Knuth relations can be generalized to these. In this extended abstract, we give an analogue of Fomin's growth diagrams for this generalized RSK correspondence on plactic biwords. We show that this growth diagram recovers the bijection between pipe dreams and bumpless pipe dreams of Gao--Huang.}

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

\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}

\begin{document}

\maketitle
The general philosophy of a \emph{growth diagram} can be thought of as translating a temporal object, i.e., an algorithm, to a spatial object, i.e., a diagrammatic encoding of the algorithm, so as to provide a powerful tool to study the algorithm, as well as an interface between combinatorial algorithms and algebraic or geometric phenomena.\footnote{We learned this philosophy from Allen Knutson.} The most classical example of a growth diagram is of the classical Robinson-Schensted (RS) correspondence, a bijection between a permutation and a pair of standard Young tableaux. 
The Robinson-Schensted-Knuth (RSK) correspondence is a generalization of the RS correspondence and is of central importance in symmetric function theory. Each variation of these correspondences has its corresponding growth diagram version.  
The RS correspondence is originally defined as an insertion algorithm on pairs of standard tableaux. The algorithm iteratively scans the permutation, inserting each time a number to the insertion tableaux, and records the position of the new entry in the recording tableaux. The growth diagram first introduced by Fomin \cite{fomin1994duality,fomin1995schensted}, however, is a two dimensional grid that can be roughly thought of as an ``enriched'' permutation matrix, with the extra information determined by certain local ``growth rules.'' Although far from apparent at a first glance, the growth diagram is a lossless encoding of the insertion algorithm. Furthermore, the growth diagram manifests many non-obvious properties of the insertion algorithm. For example, the property $w\xleftrightarrow{RS}(P,Q)$ implies $w^{-1}\xleftrightarrow{RS}(Q,P)$ can be easily seen by transposing the growth diagram. 

It is possible to give the RSK correspondence an operator theoretic interpretation through growth diagrams, and as a consequence obtain a noncommutative version of Cauchy's identity \cite{fomin1995schur}. Furthermore, growth diagrams for the RS correspondence has beautiful geometric and representation-theoretic interpretations \cite{van2000flag,rosso2010robinson,steinberg1988occurrence}. 

Beyond classical RSK, there are many examples in the literature of expressing combinatorial algorithms using growth diagrams, see, e.g., \cite{lam2010affine,lenart2010growth,patrias2018dual,thomas2009jeu}.

In \cite{HP} and \cite{huang2023knuth}, the first author and Pylyavskyy introduced a generalization of the classical RSK correspondence for Schubert polynomials, called bumpless pipe dream (BPD) RSK. As in the classical case, this generalization of RSK is defined via insertion algorithms. The algorithm takes as input a certain biword, iteratively inserts it into a bumpless pipe dream, and records the insertion via chains in mixed $k$-Bruhat order. An analogue of Knuth moves was discovered for a more restrictive set of biwords, called \emph{plactic biwords}. It is then natural to pursue a growth diagram version of his generalized RSK correspondence on plactic biwords. In this extended abstract, we describe these new growth diagrams for the RSK correspondence for plactic biwords. As an application, our growth diagram manifests the canonical bijection between pipe dreams and bumpless pipedreams of the first author and Gao \cite{gao2023canonical}. We also hope that this opens up a venue for connecting the combinatorics of this generalized RSK to its algebraic or geometric interpretations.

\section{Plactic biwords and growth rules}
\subsection{Bumpless pipe dreams}
In this subsection we recall the basic definition of bumpless pipe dreams \cite{LLS}.  A (reduced) \textbf{bumpless pipe dream} for a permutation $\pi\in S_n$ is a tiling of an $n\times n$ grid with allowable tiles $\+, \bl$, $\htile$, $\vtile$, $\rt$, and $\jt$, such that $n$ ``pipes'' traveling from the bottom of the grid to the right of the grid form, and no two pipes cross twice. The bottom of the grid is labeled with $1,\cdots, n$, and a permutation read from the pipe labels from the top to bottom on the right edge of the grid is $\pi$. We denote the set of bumpless pipe dreams for $\pi\in S_n$ with  $\BPD(\pi)$. For example, Figure \ref{fig:bpd-ex} shows a bumpless pipe dream in $\BPD(14253)$. The natural embedding of permutations $S_n\hookrightarrow S_{n+1}$ gives rise to a natural embedding of bumpless pipe dreams in the $n\times n$ grid to those in the $(n+1)\times (n+1)$ grid. 

    \begin{figure}[h!]
        \centering
        \includegraphics[scale = 0.5]{bpd-ex.eps}
        \caption{A bumpless pipe dream in $\BPD(14253)$}
        \label{fig:bpd-ex}
    \end{figure}

\subsection{Generalized Knuth relations on plactic biwords}
\begin{defn}[\cite{huang2023knuth}]
\label{def:assoc-biwords}
A biletter is a pair of positive integers $\binom{a}{k}$ where $a\le k$.
A \textbf{plactic biword} is a word of biletters $\binom{\mathbf{a}}{\mathbf{k}}=\left(\begin{smallmatrix}a_1& \cdots & a_\ell  \\ k_1 &\cdots & k_\ell  \end{smallmatrix}\right)$, where $k_i\ge k_{i+1}$ for each $i$. 
\end{defn}

\begin{defn}[\cite{huang2023knuth}]
\label{def:knuth}
We define the \textbf{generalized Knuth relations} on plactic biwords as follows:
\begin{enumerate}
    \item[(1)] $\left(\begin{smallmatrix}\cdots & b & a & c & \cdots \\ \cdots & k & k & k & \cdots\end{smallmatrix}\right)\sim \left(\begin{smallmatrix}\cdots & b & c & a & \cdots \\ \cdots & k & k & k & \cdots\end{smallmatrix}\right)$ if $a<b\le c$
    \item[(2)]$\left(\begin{smallmatrix}\cdots & a & c & b & \cdots \\ \cdots & k & k & k & \cdots\end{smallmatrix}\right)\sim \left(\begin{smallmatrix}\cdots & c & a & b & \cdots \\ \cdots & k & k & k & \cdots\end{smallmatrix}\right)$ if $a\le b< c$
    \item[(3)] $\left(\begin{smallmatrix}\cdots & a & b & \cdots \\ \cdots & k & k & \cdots\end{smallmatrix}\right)\sim \left(\begin{smallmatrix}\cdots & a & b & \cdots \\ \cdots & k+1 & k & \cdots\end{smallmatrix}\right)$ if $a\le b$
    \item[(4)] $\left(\begin{smallmatrix}\cdots & b & a & \cdots \\ \cdots & k+1 & k+1 & \cdots\end{smallmatrix}\right)\sim \left(\begin{smallmatrix}\cdots & b & a & \cdots \\ \cdots & k+1 & k & \cdots\end{smallmatrix}\right)$ if $a< b$.
\end{enumerate}

\end{defn}
Notice that these relations are only defined on plactic biwords. We do not apply the relation (3) or (4) if the resulting word is no longer plactic. 


Given a biword $Q=\left( \begin{smallmatrix}
        b_1 & b_2 & \ldots & b_\ell \\
        k_1 & k_2 & \ldots & k_\ell \\
    \end{smallmatrix} \right)$, 
\cite{HP} defines a map $\mathcal{L}(Q)=(\varphi_L(Q), ch_L(Q))$ where $\varphi_L(Q)$ is the BPD obtained by reading $Q$ from right to left and successively performing left insertion, and %$ch_L(Q)=(\id\lessdot_{k_\ell} \pi_1\lessdot_{k_\ell-1}\cdots \lessdot_{k_1}\pi_\ell=\perm(\varphi_L(D)))$,
$ch_L(Q)$ is the recording chain in mixed $k$-Bruhat order with edge labels $k_\ell,\cdots, k_1$,
as well as a map $\mathcal{R}(Q)=(\varphi_R(Q), ch_R(Q))$ where $\varphi_R(Q)$ is the BPD obtained by reading $Q$ from left to right and successively performing right insertion, and $ch_R(Q)$ is the recording chain in mixed $k$-Bruhat order with edge labels $k_1,\cdots, k_\ell$.
For details of these insertion algorithms see \cite[Section 3]{HP}. Furthermore, by \cite[Proposition 1.2]{huang2023knuth}, the insertion BPD is well-defined regardless of the choice of insertion algorithms, so we write $\varphi(D):=\varphi_R(D)=\varphi_L(D)$. For the analysis of the insertion algorithm in this paper we use $\mathcal{R}$, the right insertion algorithm.
\begin{thm}[\cite{huang2023knuth}]
\label{thm:main}
For any $D\in\BPD(\pi)$, the set of plactic biwords
\[\words(D):=\{Q: \varphi(Q)=D\}\] is connected by the generalized Knuth relations.
\end{thm}

For a biword $Q$, we define $Q_{> i}$ to be the biword obtained from $Q$ by removing all biletters $\binom{a_j}{k_j}$ with $a_j \leq i$. In particular, $Q_{>0}$ is $Q$. We have the following lemma.

\begin{lemma}\label{lem:remove_i}
    Suppose $Q$ and $Q'$ are connected by the generalized Knuth relations, then for all $i$, $Q_{>i}$ and $Q'_{>i}$ are connected by the generalized Knuth relations.
\end{lemma}

\begin{proof}
    It suffices to consider the case where $Q$ and $Q'$ are connected by one generalized Knuth relation. Observe that in all relations, if we remove the biletters $\binom{a}{k}$ and $\binom{a}{k+1}$, then the remaining biwords are the same. Thus, we can iteratively remove all biletters $\binom{1}{*}, \binom{2}{*},\ldots,\binom{i}{*}$, and after each step, either the remaining biwords are connected by the same generalized Knuth relation or they are the same biword.
    % We will proceed by induction on $i$. The base case where $i = 0$ is trivial. Suppose $Q_{>i}$ and $Q'_{>i}$ are connected by one generalized Knuth relation in Definition \ref{def:knuth}. If $a > i+1$, then $Q_{>i+1}$ and $Q'_{>i+1}$ are still connected by the same Knuth relation. If $a = i+1$, then in $Q_{>i+1}$ and $Q'_{>i+1}$, the biletter $\binom{a}{k}$ is removed, so $Q_{>i+1}$ and $Q'_{>i+1}$ are the same biword.
\end{proof}

As a result of Lemma \ref{lem:remove_i}, for any $D\in \BPD(\pi)$ and any $i$, the set of plactic words $\{ Q_{> i} ~|~ Q \in \words(D) \}$ is also connected by the generalized Knuth relations. Therefore, for any $Q\in\words(D)$, $\varphi(Q_{>i})$ is the same BPD. 

\begin{rmk}
    One could similarly define $Q_{<i}$ to be the biword obtained from $Q$ by removing all biletters $\binom{a_j}{k_j}$ with $a_j \geq i$ and ask if $Q \sim Q'$ implies $Q_{<i} \sim Q'_{<i}$ for all $i$. The answer is unfortunately no. One small example is $\left(\begin{smallmatrix} 1 & 3 & 2 \\ 3 & 3 & 3 \end{smallmatrix}\right)\sim \left(\begin{smallmatrix} 1 & 3 & 2 \\ 3 & 3 & 2 \end{smallmatrix}\right)$ but $\left(\begin{smallmatrix} 1 & 2 \\ 3 & 3 \end{smallmatrix}\right)$ and $\left(\begin{smallmatrix} 1 & 2 \\ 3 & 2 \end{smallmatrix}\right)$ are not connected by generalized Knuth relations. The reason is that if $Q$ and $Q'$ are connected by the generalized Knuth relation (3) or (4), then removing $\binom{b}{*}$ yields two different biwords.
\end{rmk}

\subsection{Jeu de taquin on BPDs}
 Given $D\in\BPD(\pi)$ with $\ell(\pi)>0$, \cite[Definition 3.1]{gao2023canonical} produces another bumpless pipe dream $\nabla D\in\BPD(\pi')$ where $\ell(\pi')=\ell(\pi)-1$. We call the $\nabla$ operator \textbf{jeu de taquin} on BPDs. 
The justification of this name is that, after applying a direct bijection between (skew) semistandard tableaux and BPDs for Grassmaninan permutations, the jeu de taquin algorithm on tableaux can be realized as a corresponding algorithm on BPDs. See \cite{huang2021schubert} for a detailed description. We will sometimes use the notation $\jdt(b,r)$ instead of $\nabla$ to emphasize that jeu de taquin starts from  position $(b,r)$. See Figure~\ref{fig:growth-ex3} for an illustration.

     For each BPD $D$, let $b$ be the smallest row with an empty square $\bl$, define $D' = \rect(D)$ be the BPD obtained from $D$ by performing $\jdt$ on all empty squares on row $b$ from right to left. Suppose $\pi$ and $\mu$ are the permutations of $D'$ and $D$, respectively, then by \cite{gao2023canonical}, we have $\mu = s_{i_j}\ldots s_{i_1}\pi$,
    % %
    % \[ \mu = s_{i_j}\ldots s_{i_1}\pi \]
    % %
    where $i_j>\ldots>i_1$. 
    % Thus, we define $I(D) = \{i_1,\ldots,i_j\}$.
    % Also, when there is little ambiguity, we denote the BPD corresponding to a permutation $\pi$ on the growth diagram as $D_\pi$.

    \begin{thm}\label{thm:jdt}
        Let $D$ be the BPD corresponding to a biword 
        %
        $w=\left( \begin{smallmatrix}
            b_1 & b_2 & \ldots & b_\ell \\
            k_1 & k_2 & \ldots & k_\ell \\
        \end{smallmatrix} \right)$
        %
        and $b = \min\{b_1,\ldots,b_\ell\}$, and let $D'$ be the BPD corresponding to $w'$ obtained by removing all biletter $\binom{b}{k_i}$ from $w$. Then $D' = \rect(D)$.
    \end{thm}

    The following corollary is immediate from Theorem \ref{thm:jdt} by \cite{gao2023canonical}.

    \begin{cor}\label{cor:jdt-si}
        With the same notation as in Theorem \ref{thm:jdt}, let $\pi$ and $\mu$ be the permutations of $D'$ and $D$, respectively, then
        %
        \[ \mu = s_{i_j}\ldots s_{i_1}\pi \]
        %
        where $i_j>\ldots>i_1$.
    \end{cor}
\subsection{Growth diagrams}
\subsubsection{Defining growth diagrams}
Given a plactic biword
    %
    $\left( \begin{smallmatrix}
        b_1 & b_2 & \ldots & b_\ell \\
        k_1 & k_2 & \ldots & k_\ell \\
    \end{smallmatrix} \right)$
    %
    and let $a = \max\{b_i~|~ 1\leq i\leq \ell\}$. We define a growth diagram to be a matrix of permutations $\pi_{i,j}$ with $0 \leq i \leq a$ and $0 \leq j \leq \ell$. The \textbf{initial condition} is $\pi_{i,0} = \text{id}$ for all $i$ and $\pi_{a,j} = \text{id}$ for all $j$. The figure below shows a generic \textbf{square} of the growth diagram.

    \[
    \begin{tikzcd}[sep=tiny]
    	\pi_{i,j-1} && \pi_{i,j} \\
    	& {\ } \\
    	\pi_{i-1,j-1} && \pi_{i-1,j}
    	\arrow[no head, from=1-1, to=1-3]
    	\arrow[no head, from=1-1, to=3-1]
    	\arrow[no head, from=3-1, to=3-3]
    	\arrow[no head, from=1-3, to=3-3]
    \end{tikzcd}
    \]
    %
    We fill the squares of the growth diagram as follows. For each biletter $\binom{b_i}{k_i}$, we put an $\times_{k_i}$ in the square whose corners are $\pi_{b_i,i-1},\pi_{b_i,i},\pi_{b_i-1,i-1},\pi_{b_i-1,i}$. In addition, in every other square between columns $i-1$ and $i$, we put a subscript $k_i$. The following figure shows an example where the biword is
    %
    $\left( \begin{smallmatrix}
        1 & 3 & 1 & 2 & 1 \\
        3 & 3 & 2 & 2 & 1 \\
    \end{smallmatrix} \right).$
    %
    \[\begin{tikzcd}[sep=tiny]
	{\pi_{3,0}} && {\pi_{3,1}} && {\pi_{3,2}} && {\pi_{3,3}} && {\pi_{3,4}} && {\pi_{3,5}} \\
	& _3 && \textcolor{red}{\times_3} && _2 && _2 && _1 \\
	{\pi_{2,0}} && {\pi_{2,1}} && {\pi_{2,2}} && {\pi_{2,3}} && {\pi_{2,4}} && {\pi_{2,5}} \\
	& _3 && _3 && _2 && \textcolor{red}{\textcolor{red}{\times_2}} && _1 \\
	{\pi_{1,0}} && {\pi_{1,1}} && {\pi_{1,2}} && {\pi_{1,3}} && {\pi_{1,4}} && {\pi_{1,5}} \\
	& \textcolor{red}{\times_3} && _3 && \textcolor{red}{\times_2} && _2 && \textcolor{red}{\times_1} \\
	{\pi_{0,0}} && {\pi_{0,1}} && {\pi_{0,2}} && {\pi_{0,3}} && {\pi_{0,4}} && {\pi_{0,5}}
	\arrow[no head, from=7-3, to=7-5]
	\arrow[no head, from=7-5, to=7-7]
	\arrow[no head, from=7-7, to=7-9]
	\arrow[no head, from=7-1, to=7-3]
	\arrow[no head, from=7-1, to=5-1]
	\arrow[no head, from=5-1, to=3-1]
	\arrow[no head, from=3-1, to=1-1]
	\arrow[no head, from=1-1, to=1-3]
	\arrow[no head, from=1-3, to=1-5]
	\arrow[no head, from=1-5, to=1-7]
	\arrow[no head, from=1-7, to=1-9]
	\arrow[no head, from=1-9, to=1-11]
	\arrow[no head, from=1-3, to=3-3]
	\arrow[no head, from=3-3, to=5-3]
	\arrow[no head, from=5-3, to=7-3]
	\arrow[no head, from=1-5, to=3-5]
	\arrow[no head, from=3-5, to=5-5]
	\arrow[no head, from=5-5, to=7-5]
	\arrow[no head, from=5-1, to=5-3]
	\arrow[no head, from=5-3, to=5-5]
	\arrow[no head, from=5-5, to=5-7]
	\arrow[no head, from=5-7, to=5-9]
	\arrow[no head, from=5-9, to=5-11]
	\arrow[no head, from=1-11, to=3-11]
	\arrow[no head, from=3-11, to=5-11]
	\arrow[no head, from=5-11, to=7-11]
	\arrow[no head, from=7-9, to=5-9]
	\arrow[no head, from=3-11, to=3-9]
	\arrow[no head, from=3-9, to=3-7]
	\arrow[no head, from=3-7, to=3-5]
	\arrow[no head, from=3-5, to=3-3]
	\arrow[no head, from=3-3, to=3-1]
	\arrow[no head, from=1-7, to=3-7]
	\arrow[no head, from=3-7, to=5-7]
	\arrow[no head, from=5-7, to=7-7]
	\arrow[no head, from=7-9, to=7-11]
	\arrow[no head, from=5-9, to=3-9]
	\arrow[no head, from=3-9, to=1-9]
    \end{tikzcd}\]

    For each point $(i,j)$ in the growth diagram, let $w(i,j)$ be the biword obtained from reading from left to right the X's to the NW of $(i,j)$. Formally speaking, $w(i,j)$ is obtained from 
    %
    $\left( \begin{smallmatrix}
        b_1 & b_2 & \ldots & b_\ell \\
        k_1 & k_2 & \ldots & k_\ell \\
    \end{smallmatrix} \right)$
    %
    by removing all biletter $\binom{b_s}{k_s}$ with $b_s \leq i$ or $s> j$. For example, in the above growth diagram, $w(1,4) = \left( \begin{smallmatrix}
        3 & 2 \\
        3 & 2 \\
    \end{smallmatrix} \right)$. Define $\pi_{i,j}$ to be the permutation of $\varphi(w(i,j))$, the bumpless pipe dream obtained by inserting $w(i,j)$.


\begin{rmk}
    When $k_1=\cdots =k_\ell=k$, we recover a version of classical growth diagrams for the RSK correspondence, where the input is a word with letters in positive numbers, the insertion object is a semistandard tableau, and the recording object is a standard tableau. However for classical Knuth relations, deleting either all of the smallest letter in a word, or all of the largest letter in a word, preserves Knuth classes. However in our generalized RSK, we may only delete the biletters with the smallest $b_i$, as stated in Lemma \ref{lem:remove_i}. 
\end{rmk}

\subsubsection{Local rules}
    \begin{thm}\label{thm:local-rule}
        Given a square with subscript $k$ as follows:

        \[
        \begin{tikzcd}[sep=tiny]
        	\pi && \sigma \\
        	& {\ } \\
        	\mu && \rho
        	\arrow[no head, from=1-1, to=1-3]
        	\arrow[no head, from=1-1, to=3-1]
        	\arrow[no head, from=3-1, to=3-3]
        	\arrow[no head, from=1-3, to=3-3]
        \end{tikzcd}
        \]
        Then one can get $\rho$ from $\pi,\mu$, and $\sigma$ by the following rules:

        \begin{enumerate}
            \item If there is no $\times$:
            \begin{enumerate}
                \item[(a)] If $\pi = \sigma$ then $\rho = \mu$.
                \item[(b)] If $\pi = \mu$ then $\rho = \sigma$.
                \item[(c)] If $\pi \neq \sigma, \mu$, then  $\mu = s_{i_j}\ldots s_{i_1}\pi$ where $I = \{i_j>\ldots>i_1\}$, and $\sigma = t_{\alpha\beta}\pi $ such that $\pi^{-1}(\alpha)\le k <\pi^{-1}(\beta)$ for some $\alpha<\beta$. 
                 Let $x := \min(I^C \cap [\alpha,\beta))$, and $A := (I^C\cap [\beta,\infty)) \cup \{x\} = \{j_1<j_2<\ldots\}$. Then $\rho = t_{j_\ell,j_{\ell+1}}\mu$ where $\ell$ is the smallest index such that $\mu^{-1}(j_\ell) \leq k < \mu^{-1}(j_{\ell+1})$.
            \end{enumerate}
            \item If there is an $\times$, then $\pi = \sigma$ and $\mu = s_{i_j}\ldots s_{i_1}\pi$ where $I = \{i_j>\ldots>i_1\}$. Let $I^C = \{j_1<j_2<\ldots\}$, then $\rho = t_{j_\ell,j_{\ell+1}}\mu$ where $\ell$ is the smallest index such that $\mu^{-1}(j_\ell) \leq k < \mu^{-1}(j_{\ell+1})$.
        \end{enumerate}
    \end{thm}


    \begin{ex}
    \label{ex:growth}
     Let the biword be
    %
    $\left( \begin{smallmatrix}
        1 & 3 & 1 & 2 & 1 \\
        3 & 3 & 2 & 2 & 1 \\
    \end{smallmatrix} \right),$
    %
    using the rules in Theorem \ref{thm:local-rule}, we have the following growth diagram.
    %
    \[\begin{tikzcd}[sep=tiny]
	12345 && 12345 && 12345 && 12345 && 12345 && 12345 \\
	& _3 && \textcolor{red}{\times_3} && _2 && _2 && _1 \\
	12345 && 12345 && 12435 && 12435 && 12435 && 12435 \\
	& _3 && _3 && _2 && \textcolor{red}{\times_2} && _1 \\
	12345 && 12345 && 12435 && 12435 && 13425 && 13425 \\
	& \textcolor{red}{\times_3} && _3 && \textcolor{red}{\times_2} && _2 && \textcolor{red}{\times_1} \\
	12345 && 12435 && 12534 && 13524 && 15324 && 25314
	\arrow[no head, from=7-3, to=7-5]
	\arrow[no head, from=7-5, to=7-7]
	\arrow[no head, from=7-7, to=7-9]
	\arrow[no head, from=7-1, to=7-3]
	\arrow[no head, from=7-1, to=5-1]
	\arrow[no head, from=5-1, to=3-1]
	\arrow[no head, from=3-1, to=1-1]
	\arrow[no head, from=1-1, to=1-3]
	\arrow[no head, from=1-3, to=1-5]
	\arrow[no head, from=1-5, to=1-7]
	\arrow[no head, from=1-7, to=1-9]
	\arrow[no head, from=1-9, to=1-11]
	\arrow[no head, from=1-3, to=3-3]
	\arrow[no head, from=3-3, to=5-3]
	\arrow[no head, from=5-3, to=7-3]
	\arrow[no head, from=1-5, to=3-5]
	\arrow[no head, from=3-5, to=5-5]
	\arrow[no head, from=5-5, to=7-5]
	\arrow[no head, from=5-1, to=5-3]
	\arrow[no head, from=5-3, to=5-5]
	\arrow[no head, from=5-5, to=5-7]
	\arrow[no head, from=5-7, to=5-9]
	\arrow[no head, from=5-9, to=5-11]
	\arrow[no head, from=1-11, to=3-11]
	\arrow[no head, from=3-11, to=5-11]
	\arrow[no head, from=5-11, to=7-11]
	\arrow[no head, from=7-9, to=5-9]
	\arrow[no head, from=3-11, to=3-9]
	\arrow[no head, from=3-9, to=3-7]
	\arrow[no head, from=3-7, to=3-5]
	\arrow[no head, from=3-5, to=3-3]
	\arrow[no head, from=3-3, to=3-1]
	\arrow[no head, from=1-7, to=3-7]
	\arrow[no head, from=3-7, to=5-7]
	\arrow[no head, from=5-7, to=7-7]
	\arrow[no head, from=7-9, to=7-11]
	\arrow[no head, from=5-9, to=3-9]
	\arrow[no head, from=3-9, to=1-9]
    \end{tikzcd}\]
    %
    Notice that in the square
    %
    \[
    \begin{tikzcd}[sep=tiny]
        \pi = 12435 && \sigma = 13425 \\
        & _2 \\
        \mu = 13524 && \rho = 15324
        \arrow[no head, from=1-1, to=1-3]
        \arrow[no head, from=1-1, to=3-1]
        \arrow[no head, from=3-1, to=3-3]
        \arrow[no head, from=1-3, to=3-3]
    \end{tikzcd}
    \]
    %
    we use rule (1c) of Theorem \ref{thm:local-rule}. In particular, we have $\pi \neq \sigma, \mu$ and $\mu = s_4s_2\pi$. Thus, $I = \{2,4\}$. Also, $\sigma = t_{23}\pi$, so $A = \{3,5,6,\ldots\}$. Since $\mu^{-1}(3) \leq k = 2 < \mu^{-1}(5)$, we have $\rho = t_{35}\mu = 15324$. On the other hand, in the square
    %
    \[
    \begin{tikzcd}[sep=tiny]
        \pi = 13425 && \sigma = 13425 \\
        & \times_1 \\
        \mu = 15324 && \rho = 25314
        \arrow[no head, from=1-1, to=1-3]
        \arrow[no head, from=1-1, to=3-1]
        \arrow[no head, from=3-1, to=3-3]
        \arrow[no head, from=1-3, to=3-3]
    \end{tikzcd}
    \]
    %
    we use rule (2) of Theorem \ref{thm:local-rule}. We have $\mu = s_4s_3\pi$, so $I = \{3,4\}$. Thus, $I^C = \{1,2,5,6,\ldots\}$. We have $\mu^{-1}(1) \leq k = 1 < \mu^{-1}(2)$, so $\rho = t_{12}\mu = 25314$.
    \end{ex}

    To check that the above growth diagram is correct, we can go through the insertion process. Figure \ref{fig:growth-ex} shows the insertion process of this biword. One can check that the permutations we obtain along the way are exactly the permutations on the bottom row of the growth diagram.

    \begin{figure}[h!]
        \centering
        \includegraphics[scale = 0.5]{growth-ex.eps}
        \caption{Insertion of $\left( \begin{smallmatrix}
        1 & 3 & 1 & 2 & 1 \\
        3 & 3 & 2 & 2 & 1 \\
    \end{smallmatrix} \right)$}
        \label{fig:growth-ex}
    \end{figure}

    On the other hand, removing all biletters $\binom{1}{k}$ in the original biword, we obtain the biword $\left( \begin{smallmatrix}
        3 & 2 \\
        3 & 2 \\
    \end{smallmatrix} \right)$. The BPD of this biword is shown in Figure \ref{fig:growth-ex2}.

    \begin{figure}[h!]
        \centering
        \includegraphics[scale = 0.5]{growth-ex2.eps}
        \caption{Insertion of $\left( \begin{smallmatrix}
        3 & 2 \\
        3 & 2 \\
    \end{smallmatrix} \right)$}
        \label{fig:growth-ex2}
    \end{figure}
    
    Let $D$ be the BPD corresponding to the original biword
    %
    $\left( \begin{smallmatrix}
        1 & 3 & 1 & 2 & 1 \\
        3 & 3 & 2 & 2 & 1 \\
    \end{smallmatrix} \right)$
    %
    (in Figure \ref{fig:growth-ex}), and $D'$ be the BPD corresponding to the new biword $\left( \begin{smallmatrix}
        3 & 2 \\
        3 & 2 \\
    \end{smallmatrix} \right)$ (in Figure \ref{fig:growth-ex2}). Theorem \ref{thm:jdt} says that $D' = \rect(D)$. This is indeed the case as shown in Figure \ref{fig:growth-ex3}.

    \begin{figure}[h!]
        \centering
        \includegraphics[scale = 0.5]{growth-ex3.eps}
        \caption{}
        \label{fig:growth-ex3}
    \end{figure}

    \begin{defn}[\cite{BJS}]\label{def:compatible-sequence}
For a permutation $\pi$ with $\ell(\pi)=\ell$, a pair of integer sequences $\big(\mathbf{a}=(a_1,\ldots,a_{\ell}),\mathbf{r}=(r_1,\ldots,r_{\ell})\big)$ is a  \textbf{bounded reduced compatible sequence} of $\pi$ if
$s_{a_1}\cdots s_{a_\ell}$ is a reduced word of $\pi$,
 $r_1\leq\cdots \leq r_{\ell}$ is weakly increasing,
 $r_j\leq a_j$ for $j=1,\ldots,\ell$, and
 $r_j<r_{j+1}$ if $a_j<a_{j+1}$.

\end{defn}
\begin{thm}
    Let $Q:=\left( \begin{smallmatrix}
        b_1 & b_2 & \ldots & b_\ell \\
        k_1 & k_2 & \ldots & k_\ell \\
    \end{smallmatrix} \right)$
    %
    and let $a = \max\{b_i~|~ 1\leq i\leq \ell\}$, and $(\pi_{i,j})_{0\le i\le a, 0\le j\le \ell}$ be the growth diagram of $Q$. Then the rightmost vertical chain
    \[\mathrm{id}=\pi_{a,\ell}\lessdot \cdots \lessdot \pi_{0,\ell}\] uniquely recovers a bounded reduced compatible sequence, and this bijects to $\varphi(Q)$ under the bijection in \cite{gao2023canonical}.


    Explicitly, by Corollary~\ref{cor:jdt-si}, for each $1\le i\le a$, we have $s_{i,m_i},\cdots s_{i,1}\pi_{i,\ell}=\pi_{i-1,\ell}$., where $s_{i,1}>\cdots >s_{i,m_i}$. Then the compatible sequence that corresponds to $Q$ is 
    \[\binom{\mathbf{a}}{\mathbf{r}}= \begin{pmatrix}
        s_{0,1} & \cdots & s_{0,m_1} & s_{1,1} & \cdots &s_{1,m_1} &\cdots & s_{a-1,1} & \cdots & s_{a-1,m_{a-1}} \\
        1 & \cdots & 1& 2 & \cdots &2 & \cdots & a & \cdots & a
    \end{pmatrix}. \]
\end{thm}
\begin{ex}
    Continuing Example~\ref{ex:growth}, the compatible sequence that corresponds to the chain
    \[12345\lessdot 12435 \lessdot 13425 \lessdot 25314\]
    is \[\binom{\mathbf{a}}{\mathbf{r}}= \begin{pmatrix}
        s_4 & s_3 & s_1 & s_2 & s_3 \\
        1 & 1 & 1 & 2 & 3 \\
    \end{pmatrix}. \]
\end{ex}
\section{Summary of proofs}

Theorem \ref{thm:jdt} follows from the following lemma, which can be proven by a technical analysis of the algorithms.

    \begin{lemma}\label{lem:jdt-commute}
        Let $D\in\BPD(\pi)$ and $D' = \nabla(D)$. Let $c$ be the smallest such that row $c$ contains a blank tile in $D$. Given $b\geq c$ and $k$ such that the smallest descent in $\pi$ is at least $k$. Then
        %
        \[ \nabla\left( D\leftarrow \binom{b}{k} \right) = D' \leftarrow \binom{b}{k}. \] 
    \end{lemma}

For Theorem \ref{thm:local-rule}, cases (1a) and (1b) follow directly from the definition of the growth diagram. It remains to prove cases (1c) and (2). The key lemma to prove these two cases is the following. We use a notion of ``insertion path'' and do a careful analysis of how the insertion algorithms interact with the pipes in $D$ and $D'$.

    \begin{lemma}\label{lem:jdt-insert}
        Let $D\in\BPD(\pi)$, and $D' = \nabla(D)$. Suppose $\pop(D) = (i,c)$, then by definition $D'\in\BPD(\sigma)$ where $\sigma = s_i\pi$. Given $b\geq c$ and $k$ such that the smallest descent in $\pi$ is at least $k$. Suppose the insertion path of $D' \leftarrow \binom{b}{k}$ goes through pipes $p_1<p_2<\ldots<p_\ell$. Let $P := \{p_1,p_2,\ldots,p_\ell\}$, then
        %
        \begin{enumerate}
            \item if $i = p_{j}$ and $i+1 \neq p_{j+1}$ for some $1\leq j\leq \ell-1$, then $D \leftarrow \binom{b}{k}$ goes through pipes $p_1,\ldots,p_{j-1},p_j+1,p_{j+1},\ldots,p_\ell$;
            % \daoji{Do you have an example where $p_{j+1},\cdots$ are non-empty?}
            %
            \item if $i = p_{\ell-1}$ and $i+1 = p_\ell$, then $D \leftarrow \binom{b}{k}$ goes through pipes $p_1,\ldots,p_{\ell-2},p_\ell,p_\ell + 1,p_\ell+2,\ldots$ until it terminates;
            %
            \item if $i = p_\ell$ then $D \leftarrow \binom{b}{k}$ goes through pipes $p_1,\ldots,p_{\ell-1},p_\ell + 1$;
            %
            \item otherwise, $D \leftarrow \binom{b}{k}$ goes through pipes $p_1,\ldots,p_\ell$.
        \end{enumerate}
        %
        In particular, unless $i = p_{\ell-1}$ or $i = p_{\ell}$, the last two pipes of $D \leftarrow \binom{b}{k}$ are still $p_{\ell-1}$ and $p_\ell$.
    \end{lemma}
    \begin{figure}[h!]
        \centering
        \includegraphics[scale = 0.6]{jdt-insert-ex12.eps}
        \caption{}
        \label{fig:jdt-insert-ex12}
    \end{figure}
    Let us give some examples of Lemma \ref{lem:jdt-insert}. In Figure \ref{fig:jdt-insert-ex12}, we have a BPD $D$ with $\pop(D) = (3,1)$. In $D' = \nabla(D)$, the insertion path of $D' \leftarrow \binom{2}{5}$ goes through pipes $2,3,5,6,7$. Since $i = 3$ is one of the pipes, but $i+1 = 4$ is not, the insertion path of $D \leftarrow \binom{2}{5}$ goes through pipes $2,4,5,6,7$. This is case (1) of Lemma \ref{lem:jdt-insert}. On the other hand, the insertion path of $D' \leftarrow \binom{1}{5}$ goes through pipes $1,2,3,4$. Since $i$ and $i+1$ are the last two pipes, the insertion path of $D \leftarrow \binom{1}{5}$ goes through pipes $1,2,4,5,6,7$. This is case (2) in Lemma \ref{lem:jdt-insert}. Finally, the insertion path of $D' \leftarrow \binom{2}{2}$ goes through pipes $2$ and $3$. Thus, the insertion path of $D \leftarrow \binom{2}{2}$ goes through pipes $2$ and $4$. This is case (3) in Lemma \ref{lem:jdt-insert}.




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