Constructing Maximal Bumpless Pipedreams for Double Grothendieck Polynomials
May 23, 2026
Abstract
Pipedreams and marked bumpless pipedreams are two combinatorial models that compute double Grothendieck polynomials. While studying matrix Schubert varieties, Pechenik, Speyer, and Weigandt defined the Rajchgot code, denoted by \(\mathsf{rajcode}(\cdot)\), which captures the leading monomial of the top-degree component of a Grothendieck polynomial. Combinatorially, their result implies that there exists a unique pipedream (or marked bumpless pipedream) with row weight \(\mathsf{rajcode}(w)\) and column weight \(\mathsf{rajcode}(w^{-1})\). A construction of such a pipedream was subsequently given by Chou and Yu. In this paper, we resolve the marked bumpless pipedream version of this problem by providing an explicit algorithm.
1 Introduction↩︎
The matrix Schubert variety \(X_w\) of a permutation \(w \in S_n\) is a generalized determinantal variety that has been studied extensively [1]–[4] due to its close relation to Schubert varieties and to the Schubert cell decomposition of the flag variety. An important invariant of such varieties is the Castelnuovo–Mumford regularity, which measures their algebraic complexity. Since matrix Schubert varieties are Cohen–Macaulay [1], [2], [5], their regularity can be computed as the degree difference between the highest and lowest degrees monomials appearing in their K-polynomial. Knutson and Miller [2] showed that the K-polynomial of \(X_w\) is the Grothendieck polynomial \(\mathfrak{G}_w(\boldsymbol{x})\). The Grothendieck polynomials are a family of polynomials introduced by Lascoux and Schützenberger to represent K-theory classes of Schubert varieties [6], [7]. Their lowest degree homogeneous components are the famous Schubert polynomials \(\mathfrak{S}_w(\boldsymbol{x})\), and their highest degree homogeneous components are the Castelnuovo–Mumford polynomials \(\mathfrak{CM}_w(\boldsymbol{x})\). Since the degrees of Schubert polynomials are known, computing the Castelnuovo–Mumford regularity of \(X_w\) is then reduced to determining the degree of \(\mathfrak{CM}_w(\boldsymbol{x})\).
With this motivation, there has been a surge in the study of the Castelnuovo–Mumford polynomials \(\mathfrak{CM}_w(\boldsymbol{x})\) [8]–[12]. The first complete characterization of their degree was given by Pechenik, Speyer, and Weigandt [13], where they defined the weak composition \(\mathsf{rajcode}(w)\) corresponding to the leading monomial of \(\mathfrak{CM}_w(\boldsymbol{x})\) under reverse lexicographic order. They computed \(\mathsf{rajcode}(w)\) by considering increasing subsequences in the one-line notation of \(w\). In addition to their formula, the climbing chain models introduced by Dreyer, Mészáros, and St. Dizier [14], and the snow diagrams introduced by Pan and Yu [15] also compute \(\mathsf{rajcode}(w)\) combinatorially.
The double Grothendieck polynomials \(\mathfrak{G}_w(\boldsymbol{x};\boldsymbol{y})\) form a refinement of Grothendieck polynomials in equivariant K-theory, with the specialization \(\mathfrak{G}_w(\boldsymbol{x}; 0) = \mathfrak{G}_w(\boldsymbol{x})\). Their highest degree homogeneous components are the double Castelnuovo–Mumford polynomials \(\mathfrak{CM}_w(\boldsymbol{x}; \boldsymbol{y})\). Pechenik, Speyer, and Weigandt showed that \(\mathsf{rajcode}(\cdot)\) also controls the leading monomial of \(\mathfrak{CM}_w(\boldsymbol{x}; \boldsymbol{y})\).
Theorem 1 ([13]). For any term order with \(x_n > \cdots > x_1\) and \(y_n > \cdots > y_1\), the leading monomial of \(\mathfrak{CM}_w(\boldsymbol{x};\boldsymbol{y})\) is \(x^{\mathsf{rajcode}(w)} y^{\mathsf{rajcode}(w^{-1})}\). Furthermore, the coefficient of this monomial is \(1\).
Pipedreams [16]–[18] and marked bumpless pipedreams [19]–[21] are certain tilings labeled by permutations that compute \(\mathfrak{G}_w(\boldsymbol{x})\) and \(\mathfrak{G}_w(\boldsymbol{x};\boldsymbol{y})\) combinatorially. The row and column weights of pipedreams (resp. marked bumpless pipedreams) are weak compositions that record the number of certain types of tiles in each row and column of the diagrams. Let \(\mathsf{PD}(w)\) and \(\mathsf{MBPD}(w)\) denote the sets of pipedreams and marked bumpless pipedreams labeled by \(w\), respectively.
Theorem 1 implies that there exists a unique pipedream (resp. marked bumpless pipedream) in \(\mathsf{PD}(w)\) (resp. \(\mathsf{MBPD}(w)\)) whose row weight is \(\mathsf{rajcode}(w)\) and column weight is \(\mathsf{rajcode}(w^{-1})\), which we call the maximal pipedream (resp. marked bumpless pipedream). Pechenik, Speyer, and Weigandt asked in their paper for an explicit algorithm that constructs the maximal pipedream for any permutation, which was subsequently given by Chou and Yu [22]. In this paper, we provide an explicit algorithm that constructs the maximal marked bumpless pipedream starting with the snow Rothe pipedream \(\mathsf{SRPD}(w)\) (see Section 2.2).
Theorem 2. For \(w \in S_n\), let \(\widehat{\mathrm{D}}(w)\) be the marked bumpless pipedream obtained by applying the algorithm in Section 3.2 to the snow Rothe pipedream of \(w\). Then \(\widehat{\mathrm{D}}(w)\) is the unique maximal marked bumpless pipedream of \(w\) with row weight \(\mathsf{rajcode}(w)\) and column weight \(\mathsf{rajcode}(w^{-1})\).
Huang, Shimozono, and Yu [23] established a canonical bijection between \(\mathsf{PD}(w)\) and \(\mathsf{MBPD}(w)\) that preserves row weights but not column weights. In fact, there does not exist a bijection between pipedreams and marked bumpless pipedreams that preserves both row and column weights. We remark that composing the constructions in [22] and [23] does yield a bumpless pipedream with row weight \(\mathsf{rajcode}(w)\), but not necessarily with column weight \(\mathsf{rajcode}(w^{-1})\) (see Example 10).
The outline of the paper is as follows. In Section 2, we introduce the necessary background. In Section 3, we describe the algorithm that constructs the maximal marked bumpless pipedream. In Section 4, we prove Theorem 2.
Acknowledgement↩︎
This work was supported by the Natural Science Foundation of Tianjin City (Grant No. 25JCQNJC00250) and the Natural Science Foundation of China (Grant No. 12001398).
We would like to thank Jack Chou, Peter Guo, Zachary Hamaker, and Tianyi Yu for helpful conversations. We thank Jack Chou for helping with earlier drafts and the exposition of this paper.
2 Background↩︎
Let \(S_n\) be the set of permutations on \([n] = \{1, \dots, n\}\). For an \(n \times n\) grid, we label the rows from top to bottom and the columns from left to right, and \((i,j)\) indicates the cell in row \(i\) and column \(j\). A diagram is a subset of the \(n \times n\) grid. A weak composition \(\alpha\) is a finite sequence of \(\mathbb{Z}_{\geqslant 0}\). We write \(\alpha_i\) for its \(i\textsuperscript{th}\) entry.
2.1 Marked bumpless pipedreams and Grothendieck polynomials↩︎
Definition 3 ([19]–[21]). A marked bumpless pipedream* is a tiling of the \(n \times n\) grid using the tiles \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \end{tikzpicture}\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \end{tikzpicture}\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) such that*
there are \(n\) total pipes,
each pipe starts from the bottom edge of the grid,
each pipe ends at the right edge of the grid.
Each marked bumpless pipedream is associated with a permutation \(w \in S_n\). We first label the pipes by the column they enter from the bottom, and trace the pipes until they exit to the right. We then read off the labeling on the right as the one-line notation of \(w\). When we read the permutation \(w\) from the diagram, if a pair of pipes cross each other more than once, we ignore all crossings after the first one. We denote the set of marked bumpless pipedreams associated with \(w\) by \(\mathsf{MBPD}(w)\).
For a marked bumpless pipedream \(P\), the row weight of \(P\) is the weak composition \(\mathsf{rwt}(P) = (r_1, \dots, r_n)\) where \(r_i\) is the number of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) and \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) in row \(i\) of \(P\). Similarly, the column weight of \(P\) is the weak composition \(\mathsf{cwt}(P) = (c_1, \dots, c_n)\) where \(c_j\) is the number of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) and \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) in column \(j\) of \(P\).
Example 1. The following are two marked bumpless pipedreams \(P_1, P_2 \in \mathsf{MBPD}(251634)\). \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/haztrcwn.png}\label{twehxskg}\end{figure} \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/owasydqc.png}\label{thwilsxp}\end{figure}\] {#eq: sublabel=eq:twehxskg,eq:thwilsxp} The weights of the marked bumpless pipedreams are \[\begin{align} \mathsf{rwt}(P_1) = (1,3,0,2,0,0), \quad \mathsf{rwt}(P_2) = (3,3,1,1,0,0),\\ \mathsf{cwt}(P_1) = (2,0,2,2,0,0), \quad \mathsf{cwt}(P_2) = (3,2,2,1,0,0). \end{align}\]
Theorem 4 ([21], Theorem 1.1). The Grothendieck polynomials* \(\mathfrak{G}_w(\boldsymbol{x})\) and double Grothendieck polynomials \(\mathfrak{G}_w(\boldsymbol{x}; \boldsymbol{y})\) are given by the following weighted sums: \[\begin{align} \mathfrak{G}_w(\boldsymbol{x}) &:=\sum_{P \in \mathsf{MBPD}(w)} (-1)^{\#\{ \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\, ,\, \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\}-\ell(w)}\prod_{(i,j)\in \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\, , \, \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}}x_i,\\ \mathfrak{G}_w(\boldsymbol{x};\boldsymbol{y})&: =\sum_{P \in \mathsf{MBPD}(w)} (-1)^{\#\{ \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\, , \, \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\}-\ell(w)}\prod_{(i,j)\in \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\, , \, \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}}(x_i+y_j-x_iy_j). \end{align}\]*
Example 2. For \(w = 1423\), there are five marked bumpless pipedreams in \(\mathsf{MBPD}(w)\). \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/hcgdimfz.png}\label{tjlacigm}\end{figure} \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/iprncdxa.png}\label{gvuolxyw}\end{figure} \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/rwdhisoy.png}\label{mxgrbqfo}\end{figure} \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/ixprfluw.png}\label{sorlmnhe}\end{figure} \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/yirltksm.png}\label{euwrdzsk}\end{figure}\] {#eq: sublabel=eq:tjlacigm,eq:gvuolxyw,eq:mxgrbqfo,eq:sorlmnhe,eq:euwrdzsk} Therefore, the Grothendieck polynomial and double Grothendieck polynomial of \(w\) are \[\begin{align} \mathfrak{G}_w(\boldsymbol{x}) = &\, x_2^2 + x_1x_2 + x_1^2 - x_1x_2^2 - x_1^2x_2,\\ \mathfrak{G}_w(\boldsymbol{x}; \boldsymbol{y}) = &\,(x_2 + y_2 - x_2y_2)(x_2 + y_3 - x_2y_3) \\ + &(x_1 + y_1 - x_1y_1)(x_2 + y_3 - x_2y_3)\\ + &(x_1 + y_1 - x_1y_1)(x_1 + y_2 - x_1y_2)\\ - &(x_1 + y_1 - x_1y_1)(x_2 + y_2 - x_2y_2)(x_2 + y_3 - x_2y_3)\\ - &(x_1 + y_1 - x_1y_1)(x_1 + y_2 - x_1y_2)(x_2 + y_3 - x_2y_3). \end{align}\]
Let \(\widehat{\mathsf{MBPD}}(w)\) denote the set of marked bumpless pipedreams in \(\mathsf{MBPD}(w)\) with maximal number of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) and \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\). We obtain the (double) Castelnuovo–Mumford polynomials by taking the highest degree terms in each product in the formula above from marked bumpless pipedreams in \(\widehat{\mathsf{MBPD}}(w)\). \[\begin{align} \mathfrak{CM}_w(\boldsymbol{x}) &= \sum_{P \in \widehat{\mathsf{MBPD}}(w)} \prod_{(i,j) = \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}, \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}} x_i = \sum_{P \in \widehat{\mathsf{MBPD}}(w)} x^{\mathsf{rwt}(P)}\\ \mathfrak{CM}_w(\boldsymbol{x}; \boldsymbol{y}) &= \sum_{P \in \widehat{\mathsf{MBPD}}(w)} \prod_{(i,j) = \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}, \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}} x_iy_j = \sum_{P \in \widehat{\mathsf{MBPD}}(w)} x^{\mathsf{rwt}(P)}y^{\mathsf{cwt}(P)} \end{align}\]
Example 3. Continuing Example 2, let \(w = 1423\). There are two marked bumpless pipedreams in \(\widehat{\mathsf{MBPD}}(w)\). \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/kwfvmzrq.png}\label{wjsocugb}\end{figure} \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/wrphysex.png}\label{gfpqixjm}\end{figure}\] {#eq: sublabel=eq:wjsocugb,eq:gfpqixjm} Therefore, the Castelnuovo–Mumford polynomial and double Castelnuovo–Mumford polynomial of \(w\) are \[\begin{align} \mathfrak{CM}_w(\boldsymbol{x}) = \,x_1x_2^2 + x_1^2x_2 \quad \text{ and } \quad \mathfrak{CM}_w(\boldsymbol{x};\boldsymbol{y}) = \,x_1x_2^2y_1y_2y_3 + x_1^2x_2y_1y_2y_3. \end{align}\]
Remark 5. Since the signs of monomials in a (double) Grothendieck polynomial alternate with degree, it could be the case that its highest degree homogeneous component consists of monomials with all negative coefficients (see Example 2). For the purposes of this paper, only the supports and weights of the top-degree terms are relevant. We therefore adopt the monomial-positive convention for the (double) Castelnuovo–Mumford polynomials.
2.2 Rajchgot code and snow diagrams↩︎
Pechenik, Speyer, and Weigandt [13] defined the Rajchgot code, denoted by \(\mathsf{rajcode}(\cdot)\), to describe the leading monomial of \(\mathfrak{CM}_w(x)\) under reverse lexicographic order. For \(w \in S_n\), they computed \(\mathsf{rajcode}(w)\) by considering longest increasing subsequences in the one-line notation of \(w\). In this paper, we use another combinatorial formula introduced by Pan and Yu as our definition of \(\mathsf{rajcode}(w)\).
The Rothe diagram of a permutation \(w\) is the diagram \(\mathsf{Rothe}(w) = \{(i,w(j)): i < j, w(i) > w(j)\}.\) For every \(w\in S_n\), there exists a unique marked bumpless pipedream whose \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) are exactly \(\mathsf{Rothe}(w)\). We call this the Rothe pipedream of \(w\) and denote it by \(\mathsf{RPD}(w)\). It is also the unique marked bumpless pipedream that does not use any \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \end{tikzpicture}\) or \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\).
Example 4. For \(w = 251634\), the diagrams \(\mathsf{Rothe}(w)\) and \(\mathsf{RPD}(w)\) are shown below. \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/gcbzokhw.png}\label{ijlzdbkx}\end{figure} \quad \quad \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/qrvysicz.png}\label{gajfmqrx}\end{figure}\] {#eq: sublabel=eq:ijlzdbkx,eq:gajfmqrx}
For a diagram \(D\), we define the dark clouds of \(D\) to be the subset \(\mathsf{dark}(D) \subseteq D\) constructed as follows: Scan through \(D\) from bottom to top. For each row \(r\), if there exists \((r,c) \in D\) such that currently there are no cells in column \(c\) of \(\mathsf{dark}(D)\), we find the largest such \(c\) and put \((r,c)\) in \(\mathsf{dark}(D)\).
Example 5. For \(w=251634\), the diagrams \(\mathsf{Rothe}(w)\) and \(\mathsf{dark}(\mathsf{Rothe}(w))\) are shown below. \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/ashvuqjm.png}\label{jdlozqvk}\end{figure} \quad \quad \quad \quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/mdofgirp.png}\label{curzjwyk}\end{figure}\] {#eq: sublabel=eq:jdlozqvk,eq:curzjwyk}
The snow diagram of \(D\), denoted as \(\mathsf{Snow}(D)\), is the diagram obtained by filling in all empty cells above \(\mathsf{dark}(D)\) in \(D\). The left snow diagram of \(D\), denoted as \(\overleftarrow{\mathsf{Snow}}(D)\), is the diagram obtained by filling in all empty cells to the left of \(\mathsf{dark}(D)\) in \(D\). We call these additional cells snow cells. For \(w \in S_n\), we further define \(\mathsf{Snow}(w) := \mathsf{Snow}(\mathsf{Rothe}(w))\) and \(\overleftarrow{\mathsf{Snow}}(w) := \overleftarrow{\mathsf{Snow}}(\mathsf{Rothe}(w))\). For each fixed pipe, the number of \(*\) in \(\mathsf{Snow}(w)\) is equal to that in \(\overleftarrow{\mathsf{Snow}}(w)\). Define \(\mathsf{SRPD}(w)\) as the diagram obtained by overlaying the \(\mathsf{Snow}(w)\) and the \(\mathsf{RPD}(w)\), i.e., a diagram that contains both pipes and \(*\).
Example 6. Continuing the previous example, we illustrate \(\mathsf{Snow}(w)\) , \(\overleftarrow{\mathsf{Snow}}(w)\) and \(\mathsf{SRPD}(w)\) for \(w = 251634\). For clarity, dark clouds are represented by black cells, while snow cells in the (left) snow diagrams are marked by stars. \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/ryzneupc.png}\label{bpgdskjy}\end{figure} \quad\quad\quad\quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/gjuechps.png}\label{ekndjciw}\end{figure} \quad\quad\quad\quad \begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/rhgavpkm.png}\label{udfkqrap}\end{figure}\] {#eq: sublabel=eq:bpgdskjy,eq:ekndjciw,eq:udfkqrap}
Definition 6. For a diagram \(D\), the row weight* of \(D\) is the weak composition \(\mathsf{rw}(D)\) where \(\mathsf{rw}(D)_i\) is the number of cells in row \(i\) of \(D\). Similarly, the column weight of \(D\) is the weak composition \(\mathsf{cw}(D)\) where \(\mathsf{cw}(D)_i\) is the number of cells in column \(i\) of \(D\).*
For each \(w\in S_n\), Pechenik, Speyer, and Weigandt originally defined the weak composition \(\mathsf{rajcode}(w)\) via increasing subsequences of \(w\). In this paper, we adopt the diagrammatic definition of Pan and Yu [15], which uses snow diagrams.
Definition 7 ([15]*Thm. 5.6). For \(w \in S_n\), \(\mathsf{rajcode}(w) := \mathsf{rw}(\mathsf{Snow}(w))\), and \(\mathsf{rajcode}(w^{-1}) := \mathsf{cw}(\overleftarrow{\mathsf{Snow}}(w))\).
Example 7. For \(w = 251634\), we compute \(\mathsf{rajcode}(w)\) and \(\mathsf{rajcode}(w^{-1})\) using the (left) snow diagrams in Example 6. By counting the number of cells in each row (resp. column) of the snow (resp. left snow) diagram, we get that \(\mathsf{rajcode}(w) = (3,3,1,2,0,0)\) and \(\mathsf{rajcode}(w^{-1}) = (3,2,2,2,0,0)\). Therefore, by Theorem 1, the leading monomial of \(\mathfrak{CM}_{251634}(\boldsymbol{x};\boldsymbol{y})\) under reverse lexicographic order is \(x_1^3x_2^3x_3^1x_4^2y_1^3y_2^2y_3^2y_4^2\).
3 Algorithm↩︎
In this section, we describe our algorithm that transforms the snow Rothe pipedream \(\mathsf{SRPD}(w)\) into the unique maximal marked bumpless pipedream of \(w\). Since we are looking for the “maximal" diagram, we mark all \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \end{tikzpicture}\) as \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\).
The algorithm begins with the snow Rothe pipedream \(\mathsf{SRPD}(w)\). Roughly speaking, the goal of the algorithm is to iteratively “release" the snow cells by modifying pipes so that these cells are converted into horizontal segments, while preserving the permutation (see Example 8). Let \(\widehat{\mathrm{D}}(w)\) denote the marked bumpless pipedream we get from applying the algorithm to \(\mathsf{SRPD}(w)\).
3.1 Notations↩︎
We first introduce some terminologies used in the algorithm. For a pipe \(p\), its starting row is \(w^{-1}(p)\) and its terminating column is \(p\). We say that a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) of a pipe is a long line if it does not lie in the starting row of that pipe.
3.2 Algorithm↩︎
The algorithm consists of two main steps, which we call “Drooping" and”Undrooping".
3.2.1 sec:Drooping↩︎
Our algorithm iterates on the pipes in reverse order of their starting row, so the algorithm begins with pipe \(w(n)\). In each step, if pipe \(p\) contains no \(*\), the pipe remains unchanged.
If pipe \(p\) contains \(t\) \(*\)s, let \((i,j)\) be the \(t^{th}\) \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) counting from the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of pipe \(p\). We redraw pipe \(p\) after replacing \((i,j)\) with a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) and continue tracing pipe \(p\) by the following local rules:
If pipe \(p\) enters column \(p\), we draw a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) followed by \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \end{tikzpicture}\)s until pipe \(p\) exits the entire diagram from the bottom.
If pipe \(p\) enters a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \end{tikzpicture}\) from the right, we replace it with a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) so pipe \(p\) exits from the left.
If pipe \(p\) enters a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) from the top, we replace it with a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) so pipe \(p\) exits from the bottom.
If pipe \(p\) enters a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) from the top, we replace it with a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) so pipe \(p\) exits from the left.
If pipe \(p\) enters a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) from the right, we replace it with a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) so pipe \(p\) exits from the bottom.
If pipe \(p\) enters a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) from the top, we replace it with a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) so pipe \(p\) exits from the left.
If pipe \(p\) enters a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) from the right, we replace it with a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) so pipe \(p\) exits from the bottom.
For the processes in (2) and (3), we say that pipe \(p\) “passes through” the existing pipe in the tile (without changing direction); the resulting \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) is termed a p-cross. For the processes in (4) and (5), we say that pipe \(p\) “contacts” the existing pipe in the tile (thereby changing direction); the resulting \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) is termed a c-cross.
3.2.2 sec:Undrooping↩︎
After redrawing each pipe, we check for long lines in all the pipes. If any long line exists, consider the topmost long line of some pipe \(q\). Denote by \((a_1, b_0)\) the position where the long line first appears.
Traverse along pipe \(q\) and locate all instances of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) (including \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\)). If \(r\) such instances exist, label them from bottom to top as \((a_1,b_1), (a_2,b_2),\ldots,(a_r,b_r)\). More specifically, denote \(a_{r+1}=w^{-1}(q)\) (see Figure 1).
We construct an operation rectangle whose SE and NW corners are \((a_i, b_i)\) and \((a_{i+1}, b_{i-1})\) for \(i= 1,2,\dots,r\). The mini-undroop (cf. [24]) repositions pipe \(q\) from the SE corner of the rectangle to its NW corner, i.e., from \((a_i, b_i)\) to \((a_{i+1}, b_{i-1})\). Figure 2 shows this configuration, with all pipes other than \(q\) omitted. The resulting diagram after such operations remains a standard marked bumpless pipedream (see Proposition 13).
We apply mini-undroop to the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) (including \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\)) that lies to the right of this long line. We repeatedly apply mini-undroops until pipe \(q\) has no long lines. Since mini-undroop strictly decreases the row index of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\)s, the sequence must terminate after finitely many steps, see Figure 3. We then continue “Undrooping" process until the entire diagram contains no long lines. Only after all long lines are resolved do we proceed with the”Drooping" algorithm to redraw the next pipe.
Example 8. Figure 4 illustrates the construction of the maximal marked bumpless pipedream associated with \(w=5241736.\) Starting from Figure 4 (a), we apply the algorithm successively through Figures 4 (b)–(e). Since no long line appears during the process, only the “Drooping” algorithm is required. In this figure, the red line marks the pipe that will execute the algorithm.
![Figure 5: The algorithm on the snow Rothe pipedream of w=[6,1,4,3,12,11,10,9,2,8,5,7].](/article/2605.24511/_pdflatex/seahxzic.png "fig:")
Example 9. In Figure 5, starting from the snow Rothe pipedream \(\mathsf{SRPD}(w)\) of \(w=[6,1,4,3,12,11,\\ 10,9,2,8,5,7]\) (Figure 5 (a)), we apply the algorithm sequentially to pipes 2, 3, 4, and 1 to obtain Figure 5 (b). The operations on these pipes are omitted here because they involve only the “Drooping” algorithm; thus, the transition from (a) to (b) is achieved directly. Next, applying the “Drooping" algorithm to pipe 6 transforms (b) into (c). This operation, in turn, sequentially triggers the”Undrooping" algorithm on pipes 1, 4, and 3, leading from (c) through to (f). The red line marks the pipe that will execute the “Undrooping" algorithm and the thick segment represents a long line.
We end this section with an example to show that this algorithm is not the composition of constructions defined by Chou and Yu [22] and Huang, Shimozono, and Yu [23].
Example 10. For \(w=21453\), the left marked bumpless pipedream is the unique maximal marked bumpless pipedream constructed from our algorithm. The right pipedream is obtained by applying the inverse of the bijection in [23] to the left marked bumpless pipedream. The right pipedream is not the unique maximal pipedream constructed in [22] since its column weight is not \((2,1,2,0,0)\).
Figure 6: |
Figure 7: |
. 
. 4 Proof of Theorem 2↩︎
We now prove that the algorithm produces the desired marked bumpless pipedream. We call the combined step of moving left and then downward a bi-step. There are four bi-steps in Figure 8, one of which is marked by a red line. Let \(num_{*}(p)\) be the number of \(*\) on pipe \(p\).
Lemma 8. (1) The number of new empty boxes generated by the “Drooping" algorithm in the starting row of pipe \(p\) is equal to the number of \(*\) on pipe \(p\).
(2) Assume that after pipe \(p\) completes the “Drooping" algorithm, there are no long lines remaining. Right after pipe \(p\) completes the algorithm, the number of empty boxes added on its left side decreases by one in each successive row that contains a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of \(p\), until it reaches zero (see Figure 9). This holds even if other pipes pass through pipe \(p\) during the process.
Proof. (1) It is clear from the algorithm.
(2) Suppose \(num_{*}(p) = t\). At the redrawing stage of pipe \(p\), once the second \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) on pipe \(p\) is generated, the number of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) newly added to the left of this \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) in that row is \(t-1\). This pattern continues, the number of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) newly added to the left side of pipe \(p\) decreases by one in each subsequent row.
It can be observed that if other pipes pass through pipe \(p\) horizontally or vertically, it does not affect the result. This is because when pipe \(p\) encounters \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) or \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \end{tikzpicture}\), the algorithm’s rule is to pass through directly. Therefore, by the definition of a bi-step, the conclusion still holds. ◻
Definition 9. For a row \(i\) containing two distinct pipes, denote the more leftward pipe as \(p\) and the more rightward pipe as \(q\). Let \(j_1\) be the largest column index such that \((i, j_1)\) contains pipe \(p\), and \(j_2\) be the smallest column index such that \((i, j_2)\) contains pipe \(q\).
The gap* between the two pipes in row \(i\) is defined as \(j_2 - j_1\).*
Lemma 10. If two pipes do not cross in \(\mathsf{RPD}(w)\), then they do not cross in any intermediate step of the algorithm.
Proof. Let pipe \(p,q\) be a pair of non-crossing pipes such that the starting row of pipe \(p\) is below the starting row of pipe \(q\), i.e. \(w^{-1}(p) > w^{-1}(q)\). Denote the terminating columns of pipes \(q\) and \(p\) as \(j_1\) and \(j_2\), respectively and their starting rows as \(i_1\) and \(i_2\). So we have that \(j_1 = q\), \(j_2 = p\), \(i_1 = w^{-1}(q)\) and \(i_2 = w^{-1}(p)\).
Case 1. First, we discuss the simplest scenario: consider a rectangle whose NW corner is at \((i_1, j_1)\) and SE corner is at \((i_1 + num_*(p)+l, j_1 + num_*(q))\), and assume that before pipe \(p\) executes the “Drooping" algorithm, there are no other pipes besides \(p\) and \(q\) within this rectangle. Suppose in this rectangle there are \(l\) empty rows and \(k\) empty columns between the two pipes, where \(k\) and \(l\) can be any positive integers.
After applying the “Drooping" algorithm on pipe \(p\), denote the row containing the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of pipe \(p\) in column \(j_2\) as \(i_3\) and the column containing \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of pipe \(p\) in row \(i_2\) as \(j_3\); formally, \(i_3 = i_2 + num_*(p), j_3 = j_2 + num_*(p)\).
We first consider the extremal case in which pipe \(q\) has the maximum possible number of \(*\). That is, below row \(i_1\) and between columns \(j_1\) and \(j_2\), there are \(k\) dark clouds; to the right of column \(j_1\) and between rows \(i_1\) and \(i_2\), there are \(l\) dark clouds. Assuming \(num_{*}(p)=t\) then \(num_{*}(q)=t+k+l\).
In row \(i_2\), pipe \(p\) begins its first bi-step by placing a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) at \((i_2,j_3)\), at which point \(j_3=j_1+t + k+1\). On the other hand, pipe \(q\) needs \(l+1\) bi-steps to reach the \(i_2\)-th row. By Lemma 8, \(k+t\) new empty boxes appear to the left of pipe \(q\) in row \(i_2\), as shown in Figure 11 (a). At this point, in row \(i_2\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of pipe \(p\) is in column \(j_3 = j_1 + k +t+1\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) of pipe \(q\) is in column \(j_1 + k +t\). So, the gap between pipe \(p\) and \(q\) in row \(i_2\) is \(1\). At the same time, pipe \(q\) requires \(t+l+1\) bi-steps to reach row \(i_3\). By Lemma 8, upon reaching this row, pipe \(q\) gains \(k\) new empty boxes on its left side, as shown in Figure 11 (b). In row \(i_3\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of pipe \(p\) is in column \(j_2 = j_1 +k+1\), \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) of pipe \(q\) is in column \(j_1 + k\). So, the gap between pipe \(p\) and \(q\) in row \(i_3\) is \(1\). By Lemma 8, they also do not cross between row \(i_2\) and \(i_3\).
If \(num_{*}(p)+k+l > num_{*}(q)\), then the horizontal gap between \(p\) and \(q\) in each relevant row is at least as large as in the extremal case considered above. In particular, the gap is always at least \(1\), and hence the two pipes do not cross.
Case 2. In this case, there exists another pipe \(r\) inside the rectangle whose NW corner is \((i_1, j_1)\) and SE corner is \((i_1 + l + num_*(p), j_1 + num_*(q))\).
If \(w^{-1}(q) < w^{-1}(r) < w^{-1}(p)\), at this point, the starting row of pipe \(r\) lies between the starting rows of pipes \(p\) and \(q\).
If \(q < r < p\), reasoning analogous to Case 1 shows that \(r\) does not cross \(p\) and \(q\) does not cross \(r\). Therefore, \(p\) and \(q\) are also disjoint, so the conclusion remains valid.
If \(r < q < p\) and there is a p-cross between pipe \(q\) and \(r\) in column \(q\) after the “Drooping” algorithm on pipe \(q\) is applied. Compared with Case 1, one of the empty rows between pipe \(p\) and \(q\) is occupied by pipe \(r\). In this situation, to the right of column \(j_1\) and between rows \(i_1\) and \(i_2\), the maximum possible number of dark clouds is \(l-1\). Hence the maximum possible value of \(num_*(q)\) decreases by 1. It follows from Case 1 that pipes \(p\) and \(q\) still do not cross.
If \(r < q < p\) and there is no \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) between pipe \(q\) and \(r\) in column \(q\) after the “Drooping" algorithm on pipe \(q\) is applied, as shown in Figure 12. According to the algorithm, pipe \(q\) can only pass through pipe \(r\) in the starting row of \(r\), that is, row \(w^{-1}(r)\). This may cause pipe \(p\) to cross pipe \(q\). Based on the Case 1, one of the empty rows between pipe \(p\) and \(q\) is occupied by pipe \(r\), resulting in the maximum possible value of \(num_*(q)\) being reduced by \(1\) compared to Case 1. We now consider the situation that pipe \(q\) has the most \(*\), that is , \(num_*(q)=t+k+l-1\). When pipe \(q\) passes through pipe \(r\), it proceeds one row farther downward. Pipe \(q\) requires \(l\) bi-steps to reach row \(i_2\), at which point it is located in column \(j_1+t+k\). Similarly, when there are \(c\) pipes analogous to \(r\), the same conclusion holds. And pipe \(p\) in row \(i_2\) is in column \(j_3 = j_1+t+k+1\). So the relative positions of pipes \(q\) and \(p\) remain the same as in Case 1. Equivalently, each additional downward passage through such a pipe reduces the maximum possible value of \(num_*(q)\) by exactly one. Abstractly, this amounts to the number of extra tiles it traverses when passing downward through pipes such as \(r\) being”offset" by the number of \(*\) that pipe \(q\) lacks. Therefore the gap between \(p\) and \(q\) remains at least \(1\), the conclusion still holds.
If \(q < p < r\) and there is a p-cross between pipe \(r\) and pipe \(p\) in column \(r\) after the “Drooping” algorithm on pipe \(r\) is applied. The same gap estimate as in the previous subcase applies, the gap between \(p\) and \(q\) remains at least \(1\). The number of extra tiles that pipe \(p\) traverses when moving leftward through pipes such as \(r\) “offsets" the number of \(*\) that pipe \(q\) lacks. Therefore, pipes \(p\) and \(q\) remain disjoint.
If \(q < p < r\) and there is no \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) between pipe \(r\) and pipe \(p\) in column \(r\) after the “Drooping” algorithm on pipe \(r\) is applied. According to the algorithm, pipe \(r\) can only pass through pipe \(p\) in the starting row of \(p\), that is, row \(w^{-1}(p)\). Pipe \(r\) triggers “Undrooping” algorithm for pipe \(p\). First, pipe \(p\) executes the “Drooping" algorithm. Since pipe \(r\) passes through pipe \(p\) at the starting row of \(p\), its first turning point shifts one column right compared to Case 1, that is, to column \(j_3 + 1\). So the first \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) appears at \((i_2,\; j_3 + 1)\). Then pipe \(r\) performs the”Drooping” algorithm,
which forces pipe \(p\) to undergo the “Undrooping” algorithm, as illustrated in Figure 13 (b). After the undrooping, pipe \(p\) returns to the position it would have had without the influence of \(r\), i.e., the same position as pipe \(p\) in Case 1, see Figure 13 (c). So the earlier conclusion remains valid. If there are \(c\) pipes analogous to \(r\), the first \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of pipe \(p\) will be located at \((i_2,\; j_3 + c)\) and requires \(c\) undrooping operations; ultimately it still returns to the position of pipe \(p\) in Case 1.
If \(w^{-1}(r) < w^{-1}(q)\), at this point, the starting row of pipe \(r\) lies above the starting row of pipe \(q\). The presence of pipe \(r\) may cause \(q\) to extend further upward, thereby increasing its distance from \(p\).
If \(w^{-1}(r) > w^{-1}(p)\), at this point, the starting row of pipe \(r\) lies below the starting row of pipe \(p\). The presence of pipe \(r\) may cause \(p\) to extend further downward, thereby increasing its distance from \(q\).
◻
Remark 11. Suppose pipes \(p\) and \(q\) cross and \(w^{-1}(p) > w^{-1}(q)\). Then during the algorithm, any p-cross generated between \(p\) and \(q\) must lie on either the starting row or the terminating column of pipe \(p\).
Lemma 12. During the algorithm, there is at most one p-cross between any two pipes. That is, the configuration shown in Figure 14 cannot occur.
Proof. Let pipe \(p\) be the pipe whose starting row is below that of pipe \(q\); i.e., \(w^{-1}(p) > w^{-1}(q)\). Assume that there is more than one p-cross between pipe \(p\) and \(q\). By Remark 11, any p-cross between \(p\) and \(q\) must lie on either the starting row or the terminating column of \(p\), see Figure 14. But in this configuration, pipe \(q\) terminates to the left of pipe \(p\), hence \(q<p\). Together with \(w^{-1}(q)<w^{-1}(p)\), this means that \(p\) and \(q\) do not cross in \(\mathsf{RPD}(w)\). By Lemma 10, they cannot cross during the algorithm, a contradiction.
◻
Lemma 12 shows that the algorithm does not create multiple p-crosses between the same pair of pipes. Thus, when the permutation is read from the resulting diagram, no additional p-cross can contribute a new inversion. Moreover, every c-cross produced by the algorithm occurs only between a pair of pipes that has already formed a p-cross; hence it does not change the set of pipe pairs that determine the permutation.
A priori, it is unclear that after each iteration of the algorithm (finishing a combined step of drooping and undrooping of a pipe), we get a marked bumpless pipedream. We now show that the diagrams we get in each intermediate step are valid marked bumpless pipedreams.
Proposition 13. At each intermediate step of the algorithm, the resulting diagram is a valid marked bumpless pipedream.
Proof. Throughout the algorithm, only the “Undrooping" process may generate tiles of other shapes. Below, we discuss this case in detail.
If pipe \(q\) passes through a certain tile while performing the “Drooping" algorithm, that tile must originally contain horizontal or vertical pipes, that is, it must have been \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) or \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \end{tikzpicture}\). After the”Drooping" algorithm on pipe \(q\), these tiles become \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\). Therefore, the shape of some tiles within the operation rectangle is fixed: the tiles between \(b_{i-1}\)-th column and \(b_i\)-th column in \(a_i\)-th row must be \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\); the tiles between \(a_i\)-th row and \(a_{i+1}\)-th in \(b_i\)-th column must be \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\).
Pipes other than \(q\) in the above \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) must go directly through the operation rectangle. Otherwise, considering the paths of the pipes, some pipe would have two p-crosses with pipe \(q\), which, by Lemma 12, is impossible. For example, in the case shown in Figure 15, let the three pipes that \(q\) passes through be \(p_1\), \(p_2\), \(p_3\); they must each directly pass through the operation rectangle either horizontally or vertically.
We call the box at the NW corner of the operation rectangle the target. For example, in Figure 15, \((a_{i+1},b_{i-1})\) is the target. It is clear from the algorithm that, in any given operation rectangle, if the target occurs in a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) or \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\), it becomes a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) or \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) after mini-undrooping.
Therefore, the undroop operation does not cause overlaps or conflicts between pipes; it may only change the positions of crossings involving certain pipes. The resulting diagram remains a standard marked bumpless pipedream. ◻
Proposition 14. The permutation remains unchanged after the algorithm, i.e., \(\widehat{\mathrm{D}}(w) \in \mathsf{MBPD}(w)\).
Proof. By Lemma 10, any pair of pipes that is noncrossing in \(\mathsf{RPD}(w)\) remains noncrossing throughout the algorithm. Thus the algorithm creates no new crossing pair. On the other hand, the local drooping and undrooping moves only move existing crossings between already-crossing pairs, and Lemma 12 prevents extra p-crosses from contributing new inversions when the permutation is read from the diagram. Hence the set of pipe pairs that determine the permutation is unchanged. Therefore the resulting marked bumpless pipedream still lies in \(\mathsf{MBPD}(w)\). ◻
Proposition 15. The marked bumpless pipedream \(\widehat{\mathrm{D}}(w)\) satisfies \(\mathsf{rwt}(\widehat{\mathrm{D}}(w))=\mathsf{rajcode}(w)\).
Proof. Suppose we discuss the change in weight of row \(i\) in the intermediate diagram \(D'\) during the algorithm. During the algorithm, the operation at the starting row of each pipe generates a number of new empty boxes equal to the number of \(*\), thus leaving the \(\mathsf{rwt}_i(D')\) unchanged, i.e. \(\mathsf{rwt}_i(D') = \mathsf{rw}_i(\mathsf{Snow}(w))\). The effects of other operations on \(\mathsf{rwt}_i(D')\) will be discussed later.
Case 1. During the drooping process, the changes in \(\mathsf{rwt}_i(D')\) are described below.
When the old pipe disappears, the following two situations may happen:
A \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\), which increases \(\mathsf{rwt}_i(D')\) by 1.
A \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\), and if it does not lie in the starting row of the pipe contained in the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) , then it becomes a long line that requires undrooping. In this case, the current row is the bottommost row affected by the undrooping operations. According to the later analysis of Case 2 (1), this will cause \(\mathsf{rwt}_i(D')\) to increase by 1 in this row.
When redrawing the pipe, two situations may arise:
A \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\), or a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\), which decreases \(\mathsf{rwt}_i(D')\) by 1.
A pipe passes downward through a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) and the tile turns into \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\). According to the algorithm, such a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) only appears in the starting row of pipe contained in that \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\).
If the pipe contained in that \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) later requires undrooping, then the current row is the topmost row affected by the undrooping operations. Based on the subsequent analysis of Case 2 (3), this will cause \(\mathsf{rwt}_i(D')\) to decrease by 1 in this row.
When Case 1 (1) occurs, \(\mathsf{rwt}_i(D')\) increases by 1; when Case 1 (2) occurs, \(\mathsf{rwt}_i(D')\) decreases by 1. Thus, after the undrooping operations generated in the above process are completed, \(\mathsf{rwt}_i(D')\) ultimately remains unchanged. We now consider the exceptional case in which the above transformation does not trigger an undrooping step. In the second item of Cases 1(1) and Case 1(2), the scenario without undrooping always occurs in the same row. Specifically, in row \(i\), a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) transforms into a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) and a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) transforms into a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\); in this case, the \(\mathsf{rwt}_i(D')\) remains unchanged. If, in row \(i\), the transformation of a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) into a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) as in Case 1(1) occurs without triggering undrooping, then the row \(i\) must be the starting row of the pipe contained in that \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\). After pipe \(p\) completes the “Drooping" algorithm, a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) on the right side of this row transforms into a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\); hence the \(\mathsf{rwt}_i(D')\) remains unchanged. If, in row \(i\), the transformation of a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) into a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) as in Case 1(2) occurs and the pipe passed through by \(p\) subsequently undergoes no undrooping (this process occurs only at the starting row of the pipe contained in that \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\)), then the transformation of a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) into a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) also occurs at a starting row, and consequently the \(\mathsf{rwt}_i(D')\) remains unchanged.
Case 2. During the undrooping process, the changes in \(\mathsf{rwt}_i(D')\) are described below. Mark the rows and columns as specified in the “Undrooping" algorithm and perform undrooping accordingly.
When \(i = a_1\), the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) changes into \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\), it increases \(\mathsf{rwt}_i(D')\) by 1.
For any \(i = a_2, a_3, \dots, a_r\), as can be observed from the “Undrooping” algorithm, the undrooping operation for a pipe is continuous: it must begin at the initial long line of the pipe and proceed until reaching the pipe’s starting row.
Let \(h = 2, 3, \dots, r\). When \(i = a_h\), during the \((h-1)\)-th mini-undroop, either a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) or a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\), which decreases \(\mathsf{rwt}_i(D')\) by 1. Then, during the \(h\)-th mini-undroop, the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\), increasing \(\mathsf{rwt}_i(D')\) by 1.
When \(i = a_{r+1}\), a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\), or a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\). This procedure decreases \(\mathsf{rwt}_i(D')\) by
So the changes in \(\mathsf{rwt}_i(D')\) for row \(i = a_2, a_3, \dots, a_r\) cancel each other out, while the changes at the row \(i = a_1\) and \(i = a_{r+1}\) need to be explained in conjunction with the drooping process. Their effects have already been described in the Case 1.
By Definition 7, \(\mathsf{rw}(\mathsf{Snow}(w)) = \mathsf{rajcode}(w)\). In summary, \(\mathsf{rwt}_i(\widehat{\mathrm{D}}(w)) = \mathsf{rw}_i(\mathsf{Snow}(w))= \mathsf{rajcode}_i(w)\) ◻
Proposition 16. The marked bumpless pipedream \(\widehat{\mathrm{D}}(w)\) satisfies \(\mathsf{cwt}(\widehat{D}(w)) =\mathsf{rajcode}(w^{-1})\).
Proof. Suppose we discuss the change in weight of column \(j\) in the intermediate diagram \(D'\) during the algorithm.
We first analyze the change in \(\mathsf{cwt}(D')\) of the terminating column caused by applying the “Drooping" algorithm to each pipe. Suppose the pipe under consideration is \(p\), and the number of \(*\) on pipe \(p\) in the \(\mathsf{Snow}(w)\) is \(t\) (i.e., \(\operatorname{num}_*(p) = t\)). By Lemma 8, the total number of bi-steps equals to \(num_{*}(p)+1\). Consider the row where the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) of pipe \(p\) lies in its terminating column after the algorithm, set it as \(i_p\). Upon reaching this tile, pipe \(p\) has completed \(t\) bi-steps and is executing the \((t+1)\)-st bi-step, having just turned downward. Hence the row \(i_p\) is equal to \(t\) plus the number of pipes that pipe \(p\) vertically passes through when being redrawn; that is, \[\label{eq1} i_p = t + \text{ \# \{ vertically passing through pipes \} }.\qquad{(1)}\] Moreover, \[\label{eq2} i_p = \text{ \# \{ \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture} \) directly above the \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) \} } + \text{ \# \{ newly generated \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) in column p\} }.\qquad{(2)}\] By Lemma 10, we obtain, \[\label{eq3} \text{ \# \{ vertically passing through pipes \} } = \text{ \# \{ \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture} \) directly above the \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) \} }.\qquad{(3)}\] From equation eq. 1 and equation eq. 3 we obtain, \[\label{eq4} i_p = t + \text{ \# \{ \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture} \) directly above the \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) \} }\qquad{(4)}\] According to equation eq. 2 and equation eq. 4 we obtain, \[\label{eq5} \text{ \# \{ newly generated \( \begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) in column p\} } = t.\qquad{(5)}\] Moreover, from the foregoing, the number of \(*\) in column \(p\) of the \(\overleftarrow{\mathsf{Snow}}(w)\) is also equal to \(t\). Thus, equation eq. 5 states that the number of \(*\) in column \(p\) of \(\overleftarrow{\mathsf{Snow}}(w)\) equals the number of \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) released in column \(p\) after applying the”Drooping" algorithm. Therefore, this operation does not change the \(\mathsf{cwt}_j(D')\), i.e. \(\mathsf{cwt}_j(D') = \mathsf{cw}_j(\overleftarrow{\mathsf{Snow}}(w))\).
Next, we discuss the change in \(\mathsf{cwt}_j(D')\) for the other operations.
Case 1. During the drooping process, the changes in \(\mathsf{cwt}_j(D')\) are described below.
When the old pipe disappears, a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\), which increases \(\mathsf{cwt}_j(D')\) by 1.
When redrawing the pipe, a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\), or a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\), which decreases \(\mathsf{cwt}_j(D')\) by 1.
Case 2. During the undrooping process, the changes in \(\mathsf{cwt}_j(D')\) are described below. Mark the rows and columns as specified in the “Undrooping" algorithm and perform undrooping accordingly.
When \(j=b_0,b_1,...,b_{r-1}\), the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\) changes into \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\), it increases \(\mathsf{cwt}_j(D')\) by 1. Either a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(1.0,0.5)--(0.5,0.5)--(0.5,0.0); \end{tikzpicture}\) or a \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) changes to \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.0); \draw(1.0,0.5)--(0.0,0.5); \end{tikzpicture}\), which decreases \(\mathsf{cwt}_j(D')\) by 1.
When \(j=b_r\), the \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \draw(0.5,1.0)--(0.5,0.5)--(0.0,0.5); \node at (0.5,0.5) {\tiny\bullet}; \end{tikzpicture}\) changes into \(\begin{tikzpicture}[x=0.8em,y=0.8em,thick,color = blue] \draw[step=1,gray,thin] (0,0) grid (1,1); \draw[color=black, thick, sharp corners] (0,0) rectangle (1,1); \end{tikzpicture}\), leaving \(\mathsf{cwt}_j(D')\) unchanged.
By Definition 7, \(\mathsf{cw}(\overleftarrow{\mathsf{Snow}}(w)) = \mathsf{rajcode}(w^{-1})\). Therefore, \(\mathsf{cwt}_j(\widehat{D}(w)) =\mathsf{cw}_j(\overleftarrow{\mathsf{Snow}}(w)) = \mathsf{rajcode}_j(w^{-1})\) ◻
Finally, we prove the main theorem of this paper.
Proof of Theorem 2. Given a snow Rothe pipedream \(\mathsf{SRPD}(w)\), applying the algorithm described in this paper yields the marked bumpless pipedream \(\widehat{\mathrm{D}}(w)\). By Proposition 14, \(\widehat{\mathrm{D}}(w) \in \mathsf{MBPD}(w)\). Moreover, Proposition 13 guarantees that every intermediate diagram generated during each step of the algorithm is a valid marked bumpless pipedream. Finally, by Proposition 15 and Proposition 16, we have \(\mathsf{rwt}(\widehat{\mathrm{D}}(w))=\mathsf{rajcode}(w)\) and \(\mathsf{cwt}(\widehat{D}(w)) =\mathsf{rajcode}(w^{-1})\). So the marked bumpless pipedream \(\widehat{\mathrm{D}}(w)\) we construct has row weight \(\mathsf{rajcode}(w)\) and column weight \(\mathsf{rajcode}(w^{-1})\).
By Theorem 1 and the monomial-positive expansion of \(\mathfrak{CM}_w(x;y)\) in terms of marked bumpless pipedreams, there is at most one marked bumpless pipedream in \(\mathsf{MBPD}(w)\) with row weight \(\mathsf{rajcode}(w)\) and column weight \(\mathsf{rajcode}(w^{-1})\). Since \(\widehat{\mathrm{D}}(w)\) constructed above has precisely these two weights, it is the unique maximal marked bumpless pipedream of \(w\). ◻