A Pipe Dream Perspective on Totally Symmetric Self-Complementary Plane Partitions

Abstract

We characterize totally symmetric self-complementary plane partitions (TSSCPP) as bounded compatible sequences satisfying a Yamanouchi-like condition. As such, they are in bijection with certain pipe dreams. Using this characterization and the recent bijection of Gao–Huang between reduced pipe dreams and reduced bumpless pipe dreams, we give a bijection between alternating sign matrices and TSSCPP in the reduced, 1432-avoiding case. We also give a different bijection in the 1432- and 2143-avoiding case that preserves natural poset structures on the associated pipe dreams and bumpless pipe dreams.

1 Introduction

Plane partitions are three-dimensional analogues of ordinary partitions. Just as partitions in an $a\times b$ are counted by a lovely formula $\binom {a+b}{a}$ , plane partitions in an $a\times b\times c$ box are enumerated by MacMahon’s product formula $\displaystyle \prod _{i=1}^a \displaystyle \prod _{j=1}^b \displaystyle \prod _{k=1}^c \displaystyle \frac {i+j+k-1}{i+j+k-2}$ [15]. In a 1986 [18], Stanley considered symmetry operations on plane partitions, namely, reflection (transpose), rotation and complementation. This yielded 10 symmetry classes of plane partitions consisting of plane partitions invariant under combinations of these operations. The plane partitions invariant under all three operations are called totally symmetric self-complementary (TSSCPP). As in the case of all plane partitions, each symmetry class has a nice enumeration. The set of TSSCPP inside a $2n\times 2n\times 2n$ box was shown in 1994 by Andrews [2] to be counted by $\displaystyle \prod _{j=0}^{n-1}\displaystyle \frac {(3j+1)!}{(n+j)!}$ . This was, at the time, the conjectured [16] number of $n\times n$ alternating sign matrices (ASM). The 1996 proofs of this conjecture [22, 13] sparked a search for a natural, explicit bijection between TSSCPP and ASM. Partial bijections have been found on small subsets, including the permutation case [20], the case of two monotone triangle diagonals [7, 5] and the $312$ -avoiding case [1]. This paper interprets TSSCPP as pipe dreams to extend the bijection of [20] to what appears to be a larger subset than any previous partial bijection; see Section 6 for discussion.

Our first main theorem is below; see Figure 1 for an example and Section 2 for the relevant definitions. Given $\pi \in S_n$ , let $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ denote the set of TSSCPP whose associated pipe dream is reduced and has permutation $\pi $ , and let $\operatorname {\mathrm {ASM}}^{red}(\pi )$ denote the set of ASM whose associated bumpless pipe dream is reduced and has permutation $\pi $ .

Figure 1 An example of the bijection of this paper. From left to right the objects are: TSSCPP, pipe dream, bumpless pipe dream, ASM. The pipe dream and bumpless pipe dream both have permutation $135264$ , which avoids $1432$ . Note the black rhombi in column k (from the left) of the TSSCPP fundamental domain correspond to the cross-tiles in row k (from the top) of the pipe dream. This equals the number of blank tiles in row k of the bumpless pipe dream, which is the number of positive inversions of row k of the ASM.

Theorem 1.1. Let $\pi \in S_n$ . There is an explicit weight-preserving injection $\varphi $ from $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ to $\operatorname {\mathrm {ASM}}^{red}(\pi )$ . If $\pi $ avoids $1432$ , then $\varphi $ is a bijection.

While the bijection of Theorem 1.1 preserves a meaningful weight on both sides, it does not, in general, preserve the natural partial order. A corollary of our second main result, Theorem 5.20, gives a different poset-preserving bijection between $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ and $\operatorname {\mathrm {ASM}}(\pi )$ in the case that $\pi $ avoids both $1432$ and $2143$ . (Note in this case, $\operatorname {\mathrm {ASM}}^{red}(\pi )=\operatorname {\mathrm {ASM}}(\pi )$ .) Theorem 5.20 itself relates the posets $\operatorname {{\mathrm {Slide}}}(\pi )$ on pipe dreams and $\operatorname {{\mathrm {Droop}}}(\pi )$ on bumpless pipe dreams of such permutations, giving a poset-preserving bijection by decomposing into Grassmannian and inverse-Grassmannian blocks.

The paper is organized as follows. Section 2 contains background on the relevant objects, including the permutation case TSSCPP bijection of [20] and the bijection of [11] between reduced pipe dreams and reduced bumpless pipe dreams, which are important ingredients in our proof of Theorem 1.1. Section 3 proves Theorem 3.3 characterizing TSSCPP as pipe dreams subject to a Yamanouchi-like condition. Section 4 concerns Theorem 1.1 and its proof. Section 5 proves Theorems 5.9, 5.12 and 5.20 relating the posets $\operatorname {{\mathrm {Droop}}}(\pi )$ and $\operatorname {{\mathrm {Slide}}}(\pi )$ in the respective cases where $\pi $ is inverse-Grassmannian, Grassmannian or avoiding both $1432$ and $2143$ . These theorems yield Corollaries 5.10, 5.14 and 5.21, which give poset-preserving bijections between $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ and $\operatorname {\mathrm {ASM}}(\pi )$ for these three types of permutations. Section 6 gives some concluding remarks.

An extended abstract of this paper was published in the proceedings of the 2023 FPSAC conference [12].

2 Background

In this section, we review relevant definitions and bijections from the literature. Subsections 2.1, 2.2, 2.4 and 2.5 review definitions of ASM, TSSCPP, bumpless pipe dreams and pipe dreams, respectively. Subsections 2.3 and 2.6 contain less-familiar bijections that are important for our main results.

2.1 Alternating sign matrices

In this subsection, we define alternating sign matrices (see, e.g., [16]) and the weight that is preserved in Theorem 1.1.

Definition 2.1. An alternating sign matrix (ASM) is a square matrix with entries in $\{0,1,-1\}$ such that the rows and columns each sum to $1$ and the nonzero entries alternate in sign across each row and across each column.

Alternating sign matrices are in bijection with configurations of the six-vertex / square ice model of statistical physics with domain wall boundary conditions; this was an essential element of the enumeration proof of [13]. The $3\times 3$ alternating sign matrices are below.

In Figure 2, left and center-left are an alternating sign matrix and its corresponding square ice configuration; the horizontal molecules correspond to $+1$ , the vertical molecules correspond to $-1$ , and all other molecules correspond to $0$ . Center-right is its six-vertex configuration, where the six molecule configurations are replaced by directed edges. Figure 2, right, shows the corresponding bumpless pipe dream, which will be discussed shortly.

Figure 2 An alternating sign matrix and its corresponding square ice configuration, six-vertex configuration and bumpless pipe dream.

An important statistic on an alternating sign matrix A is the positive inversion number:

$$\begin{align*}\nu(A) = \sum_{1\leq i< k<n}\sum_{1\leq \ell\leq j\leq n}A_{ij}A_{k\ell}. \end{align*}$$

The positive inversion number of A equals the number of vertices in the corresponding six-vertex configuration. Equivalently, $\nu (A)$ equals the number of entries $A_{ij}=0$ such that $\sum _{i'=1}^i A_{i'j} = \sum _{j'=1}^j A_{ij'} = 0$ . Let $\operatorname {\mathrm {NW}}(A)$ denote the set of matrix indices $(i,j)$ of all such entries. We use the notation $\operatorname {\mathrm {NW}}(A)$ since these $0$ entries are precisely those whose first nonzero entry to their right is a $1$ and the first nonzero entry below is a $1$ ; that is, they are north and west of $1$ entries. See, for instance, [4, Sections 2.1 and 5.2] for these well-known correspondences. The weight that is preserved in our main bijection is the following refinement of the positive inversion number statistic by row: $\operatorname {\mathrm {wt}}(A):=\prod _{(i,j)\in \operatorname {\mathrm {NW}}(A)}x_i$ . For the ASM in Figure 2, $\operatorname {\mathrm {wt}}(A)=x_1x_2x_3$ .

2.2 Totally symmetric self-complementary plane partitions

In this subsection, we define plane partitions and their symmetry classes (see, e.g., [18]). The weight that is preserved in Theorem 1.1 will be discussed in Subsection 2.3.

Definition 2.2. A plane partition t is a rectangular array of nonnegative integers $(t_{i,j})_{i,j\geq 1}$ such that $t_{i,j}\geq t_{i',j'}$ if $i\leq i'$ , $j\leq j'$ . We say t is in an $a\times b\times c$ bounding box if $t_{i,j}=0$ whenever $i>a$ or $j>b$ and $t_{i,j}\leq c$ for all $i,j$ . Let $PP(a\times b\times c)$ denote the set of plane partitions in an $a\times b\times c$ bounding box.

Remark 2.3. We can also view $t\in PP(a\times b\times c)$ as a finite set of positive integer lattice points $(i, j, k)$ with $1\leq i\leq a$ , $1\leq j\leq b$ and $1\leq k\leq c$ such that if $(i, j, k) \in t$ and $1 \leq i'\leq i$ , $1 \leq j'\leq j$ , $1 \leq k'\leq k$ , then $(i',j',k')\in t$ . This well-known bijection is given as $(i,j,k)\in t$ if and only if $t_{i,j}\geq k$ . We will use both of these characterizations in the next definition.

Definition 2.4. A plane partition t is symmetric if $t_{i,j}=t_{j,i}$ for all $i,j$ . t is cyclically symmetric if whenever $(i, j, k) \in t$ , then $(j, k, i) \in t$ as well. t is totally symmetric if it is both symmetric and cyclically symmetric so that whenever $(i, j, k) \in t$ then all six permutations of $(i, j, k)$ are also in t. The complement $t^C$ of t inside a given bounding box $a \times b \times c$ is defined as $t^C_{i,j}=c-t_{a-i+1,b-j+1}$ for all $1\leq i\leq a, 1\leq j\leq b$ . That is, $t^C_{i,j}$ equals the number of empty cubes above $t_{a-i+1,b-j+1}$ in the bounding box. A plane partition t is self-complementary inside a given bounding box if $t=t^C$ . A totally symmetric self-complementary plane partition (TSSCPP) is a plane partition which is both totally symmetric and self-complementary.

Note that for there to exist a self-complementary plane partition in an $a\times b\times c$ bounding box, the volume $abc$ of the box must be an even number. In addition, cyclic symmetry requires $a=b=c$ , therefore, we need $a=b=c=2n$ for there to exist a TSSCPP inside an $a\times b\times c$ bounding box.

Definition 2.5. Let $\operatorname {\mathrm {TSSCPP}}(n)$ denote the set of TSSCPP inside a $2n\times 2n\times 2n$ box.

2.3 TSSCPP Boolean triangles and a permutation case bijection

In this subsection, we review the characterization from [20] of TSSCPP as Boolean triangles and the bijection of the same paper between permutation matrices and TSSCPP Boolean triangles whose entries weakly decrease along rows. We also describe the weight on TSSCPP preserved in Theorem 1.1.

Definition 2.6 (Definition 2.12 of [20]).

A TSSCPP Boolean triangle of order n is a triangular integer array $b=\{b_{i,j}\}$ for $1 \leq i \leq n - 1$ , $n - i \leq j \leq n - 1$ with entries in $\{0, 1\}$ such that the diagonal partial sums satisfy the following inequality for all $1\leq j< i\leq n-1$ :

(2.1) $$ \begin{align} 1 + \sum_{k=j+1}^{i} b_{k,n-j-1}\geq \sum_{k=j}^{i} b_{k,n-j}. \end{align} $$

Call this the $(i,j)$ -inequality, in which $n-j$ and $n-j-1$ are the diagonals being compared and i indicates the row index of where the sums stop.

We give below the indexing of a generic TSSCPP Boolean triangle.

$$\begin{align*}\begin{array}{ccccccccccc} & & & & & b_{1,n-1} & & & & & \\ & & & & b_{2,n-2} & & b_{2,n-1} & & & & \\ & & & b_{3,n-3} & & b_{3,n-2} & & b_{3,n-1} & & & \\ & & & & & \vdots & & & & &\\ & & b_{n-1,1} & & b_{n-1,2} & \cdots & b_{n-1,n-2} & & b_{n-1,n-1}. & & \end{array}\end{align*}$$

Below are a nonexample and an example of a TSSCPP Boolean triangle.

$$\begin{align*}\begin{array}{ccccccccccc} & & & & & 1 & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 1 & & 0 & & 0 & & & \\ & & 1 & & 0 & & 0 & & 1 & & \\ & 0 & & 0 & & 0 & & 1 & & 0 &\end{array} \hspace{1cm} \begin{array}{ccccccccccc} & & & & & 1 & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 1 & & 0 & & 0 & & & \\ & & 1 & & 0 & & 1 & & 1 & & \\ & 0 & & 0 & & 0 & & 0 & & 0. &\end{array} \end{align*}$$

In the left triangle, the $(4,1)$ -inequality is not satisfied since $\sum _{k=1}^{4} b_{k,n-1} = 3$ while $\sum _{k=2}^{4} b_{k,n-2} = 1$ . In the triangle on the right, all $(i,j)$ -inequalities are satisfied.

Proposition 2.7 (Proposition 2.13 of [20]).

TSSCPP Boolean triangles of order n are in bijection with $\operatorname {\mathrm {TSSCPP}}(n)$ .

The bijection proceeds by taking the fundamental domain of the TSSCPP, transforming it into a nest of nonintersecting lattice paths, and then recording the two different types of steps in each path as $0$ and $1$ . The diagonal partial sum condition (2.1) is equivalent to the requirement that the paths do not intersect. See [20] for details.

We now review the characterization of a certain subset of TSSCPP Boolean triangles.

Definition 2.8 (Definition 3.1 of [20]).

A permutation TSSCPP Boolean triangle is a TSSCPP Boolean triangle with weakly decreasing rows.

That is, the entries equal to one in a permutation TSSCPP Boolean triangle are all left justified. The terminology ‘permutation’ in the above definition is justified by the weight-preserving bijection in the theorem below. An example of this bijection is given in Figure 3.

Figure 3 An example of the permutation case bijection of [20, Theorem 3.5].

Theorem 2.9 (Theorem 3.5 of [20]).

There is a natural, statistic-preserving bijection between $n\times n$ permutation matrices with inversion number p and permutation TSSCPP Boolean triangles of order n with p zeros.

The injection $\varphi $ in Theorem 1.1 extends this bijection under the mild transformation of flipping the resulting matrix vertically (or reversing the one-line notation of the permutation). Thus, in Theorem 1.1 we instead map the TSSCPP in Figure 3, left, to the vertical reflection of the matrix in Figure 3, right.

The TSSCPP weight preserved in Theorem 1.1 is the number of $1$ entries in the kth row from the bottom in its Boolean triangle. More specifically, for $T\in \operatorname {\mathrm {TSSCPP}}(n)$ with Boolean triangle b, let $\text {one}(T)$ denote the set of indices of the entries of b that equal $1$ . Then $\operatorname {\mathrm {wt}}(T):=\prod _{(i,j)\in \text {one}(T)}x_{n-i}$ . For the TSSCPP in Figure 3, $\operatorname {\mathrm {wt}}(T)=x_1x_3^2x_5$ and for the TSSCPP in Figure 5, $\operatorname {\mathrm {wt}}(T)=x_2^2x_3x_4$ . Note the weight can also be seen directly on the TSSCPP fundamental domain, as each $1$ in row $n-k$ of b corresponds to a black rhombus in column k (from the left) of the fundamental domain, as shown in these figures.

2.4 Bumpless pipe dreams

In this subsection, we define bumpless pipe dreams and describe the bijection with alternating sign matrices.

Definition 2.10. A bumpless pipe dream (BPD) [14] of size n is a tiling of an $n\times n$ grid of squares by the following six types of tiles: , , , , , , such that n pipes traveling from the south border to the east border are formed. We denote the set of bumpless pipe dreams of size n as $\operatorname {\mathrm {BPD}}(n)$ . We say a bumpless pipe dream is reduced if no two pipes cross twice. We associate a permutation to each reduced bumpless pipe dream by labeling the pipes $1,\cdots , n$ from left to right on the south border and read off the pipe labels from top to bottom on the east border. Let $\operatorname {\mathrm {BPD}}^{red}(\pi )$ denote the set of all reduced bumpless pipe dreams with permutation $\pi $ .

A simple droop is a move on a bumpless pipe dream bounded by a $2\times 2$ square, as shown below. The four pairs of $2\times 2$ squares show all four possibilities a pipe enters and leaves the $2\times 2$ square.

For each reduced bumpless pipe dream D, we define its weight to be the monomial $\operatorname {\mathrm {wt}}(D):=\prod _{(i,j)\in \operatorname {\mathrm {blank}}(D)}x_i$ , where $\operatorname {\mathrm {blank}}(D)$ denotes the set of the -tiles in D.

There is a natural, weight-preserving bijection between $\operatorname {\mathrm {BPD}}(n)$ and $\operatorname {\mathrm {ASM}}(n)$ , as described in [21]. To obtain an ASM from a BPD we simply replace each with a 1, each with a $-1$ , and the other four allowed squares with 0s. The blank tiles of a BPD D correspond to the NW zeros of the associated ASM A. Thus $\operatorname {\mathrm {blank}}(D)=NW(A)$ , so $\operatorname {\mathrm {wt}}(D)=\operatorname {\mathrm {wt}}(A)$ . For the inverse map, it is not difficult to see the positions of and uniquely determine a bumpless pipe dream. See Figure 2 for an example.

2.5 Pipe dreams

In this subsection, we define pipe dreams and bounded compatible sequences and describe the bijection between them.

Definition 2.11. A pipe dream (PD) [3] of size n is a tiling of an $n\times n$ grid of squares with two kinds of tiles, the cross-tile and elbow-tile , such that the positions on or below the main (anti)diagonal only consist of elbow-tiles. We think of a pipe dream as n pipes, labelled $1,\cdots , n$ traveling from the north border and exiting from the west border. We denote the set of pipe dreams of size n as $\operatorname {\mathrm {PD}}(n)$ . We say a pipe dream is reduced if no two pipes cross twice. We associate a permutation to each reduced pipe dream by reading from top to bottom the labels of each pipe on the west border of the pipe dream. (One can also assign permutations to nonreduced pipe dreams, but this will not be important for the present paper.) Let $\operatorname {\mathrm {PD}}^{red}(\pi )$ denote the set of reduced pipe dreams with permutation $\pi $ .

The set of pipe dreams for a fixed permutations are connected by chute and ladder moves. For precise definitions, see [3]. When a ladder (or chute) move is bounded by a $2\times 2$ square, we call this move a simple slide, as shown below.

Figure 4 shows the set of pipe dreams $\operatorname {\mathrm {PD}}^{red}(1432)$ . The first four pipe dreams are connected by simple slides; the fifth is not.

Figure 4 $\operatorname {\mathrm {PD}}^{red}(1432)$ .

For each pipe dream D, we define its weight to be the monomial $\operatorname {\mathrm {wt}}(D):=\prod _{(i,j)\in \operatorname {\mathrm {cross}}(D)}x_i$ , where $\operatorname {\mathrm {cross}}(D)$ denotes the set of the -tiles in D.

Definition 2.12. A bounded compatible sequence [6] is a pair $(\mathbf {a},\mathbf {r})$ , where $\mathbf {a}=(a_1,\cdots , a_{\ell })$ and $\mathbf {r}=(r_1,\cdots , r_\ell )$ are words of positive integers, satisfying the following conditions:

1. (a) $r_1\ge r_2\ge \cdots \ge r_\ell $ ,

2. (b) $a_i\ge r_i$ for all $1\le i\le \ell $ ,

3. (c) $r_i>r_{i+1}$ if $a_i\ge a_{i+1}$ .

There is a simple bijection between $\operatorname {\mathrm {PD}}(n)$ and the set of all bounded compatible sequences where $a_i<n$ for each i; see [3]. Given a bounded compatible sequence $(\mathbf {a},\mathbf {r})$ , we may construct a pipe dream by putting a cross-tile at position $(r_i, a_i+1-r_i)$ for each $1\le i\le \ell $ and fill the remaining positions with elbow-tiles. Conversely, given a pipe dream, we may construct a bounded compatible sequence as follows: Scan the pipe dream from bottom to top and within each row left to right, and whenever we encounter a cross-tile at position $(r,c)$ we append $(r+c-1,r)$ to the compatible sequence. For example, the corresponding bounded compatible sequences for the pipe dreams in Figure 4 are as follows; the vector $\mathbf {a}$ is recorded in the top row and $\mathbf {r}$ in the bottom row.

$$\begin{align*}\left(\begin{smallmatrix}3 & 2 & 3\\ 3 & 2 & 2\end{smallmatrix}\right), \left(\begin{smallmatrix}3 & 2 & 3\\ 3 & 2 & 1\end{smallmatrix}\right), \left(\begin{smallmatrix}3 & 2 & 3\\ 3 & 1 & 1\end{smallmatrix}\right), \left(\begin{smallmatrix}3 & 2 & 3\\ 2 & 1 & 1\end{smallmatrix}\right), \left(\begin{smallmatrix}2 & 3 & 2\\ 2 & 2 & 1\end{smallmatrix}\right).\end{align*}$$

2.6 Reduced BPD-PD bijection

Both reduced pipe dreams and reduced bumpless pipe dreams give combinatorial formulas for Schubert polynomials $\mathfrak {S}_\pi $ , $\pi \in S_\infty $ which are important polynomials in the study of Schubert calculus [3, 14]. Explicitly,

$$\begin{align*}\mathfrak{S}_\pi=\sum_{D\in\operatorname{\mathrm{PD}}^{red}(\pi)}\prod_{(r,c)\in\operatorname{cross}(D)}x_r=\sum_{D\in\operatorname{\mathrm{BPD}}^{red}(\pi)}\prod_{(r,c)\in\operatorname{blank}(D)}x_r.\end{align*}$$

For this reason, there exists a weight-preserving bijection between $\operatorname {\mathrm {PD}}^{red}(\pi )$ and $\operatorname {\mathrm {BPD}}^{red}(\pi )$ , where the weight of a PD or BPD is its monomial contribution to the Schubert polynomial indexed by its permutation.

In [11], such an explicit direct bijection $\varphi :\operatorname {\mathrm {BPD}}^{red}(\pi )\rightarrow \operatorname {\mathrm {PD}}^{red}(\pi )$ is given using an iterative algorithm. To find the image of a BPD under $\varphi $ , the algorithm computes in each iteration the position of one crossing in the corresponding PD. For a detailed description of this process, see [11, Definition 3.1]. For explicit examples, see [11, Example 3.4]. This bijection is weight preserving; in particular, for $D\in \operatorname {\mathrm {BPD}}^{red}(\pi )$ , the number of blank tiles in row k equals the number of cross-tiles in row k of $\varphi (D)$ .

Because the bijection is weight preserving and there is a unique lowest weight monomial that corresponds to the Lehmer code of the permutation in each Schubert polynomial, the permutation BPD is mapped to the bottom pipe dream, the unique pipe dream with all crosses left justified.

3 Characterizing TSSCPP as pseudo-Yamanouchi pipe dreams

This section focuses on our first theorem: a characterization of TSSCPP as a subset of all (reduced and nonreduced) pipe dreams.

3.1 Mapping TSSCPP into pipe dreams

Recall the bijection of Proposition 2.7 from TSSCPP to the TSSCPP Boolean triangles of Definition 2.6. As TSSCPP Boolean triangles are triangular arrays with entries in $\{0,1\}$ , we can transform them to pipe dreams (reduced and nonreduced) since these are triangular arrays of tiles with two choices for each spot. There are several possibilities for how to do this; we choose to correspond each $1$ to a cross-tile and each $0$ to an elbow-tile . There are also several choices for orientation of the triangle. We set the following convention.

Given a TSSCPP Boolean triangle b of order n, we create a triangular array $y_{i,j}$ , $1\leq i\leq n-1$ , $1\leq j\leq n-i$ of zeros and ones where $y_{i,j}=b_{n-i,i+j-1}$ . That is, we flip b vertically and justify to the left.

$$\begin{align*}\begin{array}{ccccc} b_{n-1,1} & b_{n-1,2} & b_{n-1,3} & \cdots & b_{n-1,n-1} \\ b_{n-2,2} & b_{n-2,3} & \cdots & b_{n-2,n-1} \\ b_{n-3,3} & \cdots & b_{n-3,n-1} \\ & \unicode{x22F0}\\ b_{1,n-1} \end{array} \begin{array}{ccccc} y_{1,1} & y_{1,2} & y_{1,3} & \cdots & y_{1,n-1} \\ y_{2,1} & y_{2,2} & \cdots & y_{2,n-2} & \\ y_{3,1} & \cdots & y_{3,n-3} & & \\ & \unicode{x22F0} & & & \\ y_{n-1,1} \end{array}\end{align*}$$

The inequality of Definition 2.6 translates to the following:

$$\begin{align*}1 + \sum_{k=1}^i y_{j-k,k}\geq \sum_{k=1}^{i+1} y_{j-k+1,k} \text{ for all }1\leq i< j\leq n-1.\end{align*}$$

Now, we turn each $1$ into a cross-tile and each $0$ into an elbow-tile . We call the pipe dreams that lie in this image the TSSCPP pipe dreams. Note that permutation TSSCPP Boolean triangles have weakly decreasing rows; this corresponds to left-justified crosses in the associated pipe dream.

3.2 A Yamanouchi-like condition on bounded compatible sequences

In this subsection, we prove Theorem 3.3 characterizing TSSCPP pipe dreams. We also prove Lemma 3.2, which will be used in Section 4.

Definition 3.1. Given a bounded compatible sequence

$$\begin{align*}(\mathbf{a},\mathbf{r})=((a_1,\cdots, a_\ell), (r_1,\cdots, r_\ell)),\end{align*}$$

define $\operatorname {\mathrm {count}}(k,j)(\mathbf {a})$ (or $\operatorname {\mathrm {count}}(k,j)$ when $\mathbf {a}$ is understood) to be the number of j that appear in $a_1,\cdots , a_k$ . We say that $(\mathbf {a}, \mathbf {r})$ is pseudo-Yamanouchi if for all $1\le k\le \ell $ , $1\le j\le n-2$ , $1+\operatorname {\mathrm {count}}(k,j)\ge \operatorname {\mathrm {count}}(k,j+1)$ . We also say that a pipe dream is pseudo-Yamanouchi if its corresponding bounded compatible sequence is so.

Figure 5 An example of transforming a TSSCPP to a pipe dream. Note the weight of this TSSCPP is $x_2^2x_3x_4$ .

Lemma 3.2. For any $\pi $ , the bottom pipe dream is pseudo-Yamanouchi.

Proof. The bottom pipe dream is the unique pipe dream of $\pi $ with all left-justified cross-tiles. Thus, the bounded compatible sequence $(\mathbf {a},\mathbf {r})$ is either empty or $\mathbf {a}$ is made up of increasing runs such that it can be written for some $m\geq 1$ as

$$\begin{align*}\mathbf{a}=(j_1,j_1+1,\ldots, j_1^*-1, j_1^*, j_2, j_2+1,\ldots,j_2^*-1, j_2^*, \ldots, j_{m}, j_{m}+1, \ldots, j_m^*-1, j_{m}^*),\end{align*}$$

where $j_1>j_2>\cdots >j_{m}$ and $j_i^*\geq j_i$ for all $1\leq i\leq m$ . Because $j_1>j_2>\cdots >j_{m}$ , each increasing run needs to start with a smaller number than the previous.

Suppose $(\mathbf {a},\mathbf {r})$ is not pseudo-Yamanouchi. Choose the smallest k such that there exists a j for which $1+\operatorname {\mathrm {count}}(k,j) < \operatorname {\mathrm {count}}(k,j+1)$ . Since $\operatorname {\mathrm {count}}(k,j)$ is a nonnegative increasing function of k, it must be that $1+\operatorname {\mathrm {count}}(k-1,j) = \operatorname {\mathrm {count}}(k-1,j+1)$ and $a_k=j+1$ since we chose k to be the smallest value with the property. If we are in row $j+1$ ( $r_k = j+1$ ), then this is the first time that $j+1$ has appeared in $\mathbf {a}$ , so $\operatorname {\mathrm {count}}(k,j+1) = 1$ and thus cannot be greater than $1+\operatorname {\mathrm {count}}(k,j)$ . If $r_k>j+1$ , then $a_{k-1}=j$ since the cross-tiles are left justified, and thus $\operatorname {\mathrm {count}}(k-1,j) + 1 =\operatorname {\mathrm {count}}(k,j)$ . But $1+\operatorname {\mathrm {count}}(k-1,j) \ge \operatorname {\mathrm {count}}(k-1,j+1) = \operatorname {\mathrm {count}}(k,j+1)-1$ . So finally, $\operatorname {\mathrm {count}}(k,j) \ge \operatorname {\mathrm {count}}(k,j+1)-1$ , which is a contradiction.

Theorem 3.3. $\operatorname {\mathrm {TSSCPP}}(n)$ is in weight-preserving bijection with the set of pseudo-Yamanouchi pipe dreams in $\operatorname {\mathrm {PD}}(n)$ .

Proof. We identify a TSSCPP with the 0-1 triangular array $(y_{i,j})_{1\le i\le n-1, 1\le j\le n-i}$ satisfying the inequalities $1 + \sum _{k=1}^i y_{j-k,k}\geq \sum _{k=1}^{i+1} y_{j-k+1,k}$ for all $1\leq i< j\leq n-1$ , as described in Section 3.1. These inequalities mean the following: For any position $(i,j)$ in the corresponding pipe dream, the number of crosses in the same diagonal as $(i,j)$ at or below row i can be at most one more than the number of crosses in the previous diagonal at or below row i. Therefore, it suffices to check this property when $(i,j)$ is a cross to decide whether the pipe dream is TSSCPP.

Now, suppose $(a,r)$ is an entry of a pseudo-Yamanouchi compatible sequence. Then by the definition of the reading order, all crosses that appear at or below row r in the $(a-1)$ st diagonal of the corresponding pipe dream appear before $(a,r)$ in the compatible sequence. Therefore, the inequality for the $(r,a-r+1)$ position is implied by the pseudo-Yamanouchi property. The converse is true by a similar argument.

By definition, $\operatorname {\mathrm {wt}}(T)=\operatorname {\mathrm {wt}}(D)$ , where T is a TSSCPP and D its corresponding pseudo-Yamanouchi pipe dream. So this bijection is weight preserving.

See Figure 5 for an example.

4 A bijection between TSSCPP and ASM in the reduced, 1432-avoiding case

In this section, we prove our first main result, Theorem 1.1. The proof uses the following theorem and lemmas, the first of which is due to Yibo Gao.

We need the following terminology. A permutation $\pi $ avoids a permutation $\pi '$ if there is no subsequence of $\pi $ having the same relative order as $\pi '$ .

Theorem 4.1 [10, Theorem 4.1].

If $\pi \in S_n$ avoids $1432$ , then any two reduced pipe dreams of $\pi $ are connected by simple slides.

Lemma 4.2. Suppose $D\in \operatorname {\mathrm {PD}}(n)$ is pseudo-Yamanouchi and $D'\in \operatorname {\mathrm {PD}}(n)$ is related to D by a simple slide. Then $D'$ is pseudo-Yamanouchi.

Proof. Suppose $D\in \operatorname {\mathrm {PD}}(n)$ is pseudo-Yamanouchi. Let $(\mathbf {a},\mathbf {r})=((a_1,\cdots , a_\ell ), (r_1,\cdots , r_\ell ))$ be its associated bounded compatible sequence. Suppose for some $1<i<n$ , D has a tile at position $(r_i,a_i+1-r_i)$ and no tiles at positions $(r_i,a_i+2-r_i)$ , $(r_{i}-1,a_i-r_i)$ , or $(r_{i}-1,a_i+1-r_i)$ . Then a simple slide may be applied to D, resulting in another pipe dream $D'$ with tile at position $(r_{i}-1,a_i+1-r_i)$ and no tiles at positions $(r_{i},a_i+1-r_i)$ , $(r_i,a_i+2-r_i)$ , or $(r_{i}-1,a_i-r_i)$ . That is, the simple slide moves the tile up one unit and to the right one unit and there were no other tiles in these intermediate squares. This preserves the diagonal but decrements the row index, creating a new bounded compatible sequence $(\mathbf {a}',\mathbf {r}')=((a_1',\cdots , a_{\ell }'), (r_1',\cdots , r_{\ell }'))$ such that

(4.1) $$ \begin{align} a_k'=\begin{cases} a_k & k<i \\ a_{k+1} & i\leq k < m \\ a_i & k=m \\ a_k & m<k\leq\ell, \end{cases} \end{align} $$

where $m>i$ is uniquely chosen so that $(\mathbf {a}',\mathbf {r}')$ satisfies the conditions of a bounded compatible sequence. Let $\tilde {j}:=a_i$ . So $\mathbf {a}$ and $\mathbf {a}'$ differ only in that $\tilde {j}$ has slid to the right from index i to m.

Recall $\operatorname {\mathrm {count}}(k,j)(\mathbf {a})$ denotes the number of j that appear in $a_1,\cdots , a_k$ . By assumption, $(\mathbf {a}, \mathbf {r})$ is pseudo-Yamanouchi, so for all $1\le k\le \ell $ , $1\le j\le n-2$ , $1+\operatorname {\mathrm {count}}(k,j)(\mathbf {a})\ge \operatorname {\mathrm {count}}(k,j+1)(\mathbf {a})$ . We need only check that $(\mathbf {a}', \mathbf {r}')$ is also pseudo-Yamanouchi. The only values of j we need to consider are $\tilde {j}-1$ , $\tilde {j}$ , and $\tilde {j}+1$ .

By (4.1), $\operatorname {\mathrm {count}}(k,j)(\mathbf {a}')=\operatorname {\mathrm {count}}(k,j)(\mathbf {a})$ for all values of j when $k<i$ or $k\geq m$ . Thus, we need only check the pseudo-Yamanouchi inequality for k in the range $i\leq k<m$ .

Suppose $i\leq k < m$ . Since $(\mathbf {a},\mathbf {r})$ and $(\mathbf {a}',\mathbf {r}')$ are related by a simple slide, we know there is no cross in D at position $(r_{i-1}, a_i - r_i)$ . That is, $a_{m-1}\neq \tilde {j}-1$ . Furthermore, $a_k\neq \tilde {j}-1$ for all $i\leq k < m$ . Thus, $\operatorname {\mathrm {count}}(k,\tilde {j}-1)(\mathbf {a}')=\operatorname {\mathrm {count}}(k,\tilde {j}-1)(\mathbf {a})$ for all $i\leq k < m$ while $\operatorname {\mathrm {count}}(k,\tilde {j})(\mathbf {a}')=\operatorname {\mathrm {count}}(k,\tilde {j})(\mathbf {a})-1$ in this same range. So

$$\begin{align*}\operatorname{\mathrm{count}}(k,\tilde{j}-1)(\mathbf{a}')=\operatorname{\mathrm{count}}(k,\tilde{j}-1)(\mathbf{a}) \ge \operatorname{\mathrm{count}}(k,\tilde{j})(\mathbf{a})-1 =\operatorname{\mathrm{count}}(k,\tilde{j})(\mathbf{a}').\end{align*}$$

So the pseudo-Yamanouchi condition is more than satisfied when comparing diagonals $\tilde {j}-1$ and $\tilde {j}$ .

Since $(\mathbf {a},\mathbf {r})$ and $(\mathbf {a}',\mathbf {r}')$ are related by a simple slide, we also know there is no cross in D at position $(r_i, a_i+2 - r_i)$ . That is, $a_{i+1}\neq \tilde {j}+1$ . Furthermore, $a_k\neq \tilde {j}+1$ for all $i\leq k < m$ . Thus, $\operatorname {\mathrm {count}}(k,\tilde {j}+1)(\mathbf {a}')=\operatorname {\mathrm {count}}(k,\tilde {j}+1)(\mathbf {a})$ for all $i\leq k < m$ while $\operatorname {\mathrm {count}}(k,\tilde {j})(\mathbf {a}')=\operatorname {\mathrm {count}}(k,\tilde {j})(\mathbf {a})-1$ in this same range. So

$$\begin{align*}1+\operatorname{\mathrm{count}}(k,\tilde{j})(\mathbf{a}')=1+\operatorname{\mathrm{count}}(k,\tilde{j})(\mathbf{a}) \ge \operatorname{\mathrm{count}}(k,\tilde{j}+1)(\mathbf{a}) =\operatorname{\mathrm{count}}(k,\tilde{j}+1)(\mathbf{a}').\end{align*}$$

Thus, the pseudo-Yamanouchi condition is satisfied on diagonals $\tilde {j}$ and $\tilde {j}+1$ .

Therefore, $(\mathbf {a}',\mathbf {r}')$ is pseudo-Yamanouchi, implying $D'$ is pseudo-Yamanouchi.

Lemma 4.3. If $\pi \in S_n$ avoids $1432$ , then all reduced pipe dreams of $\pi $ are pseudo-Yamanouchi.

Proof. Choose $\pi \in S_n$ that avoids $1432$ . Using the previous two lemmas, we know that simple slides preserve the pseudo-Yamanouchi property and that all reduced pipe dreams in $\operatorname {\mathrm {PD}}^{red}(\pi )$ are connected by simple slides. So we need only show one reduced pipe dream is pseudo-Yamanouchi, and then all of them are. By Lemma 3.2, the bottom (permutation) pipe dream is pseudo-Yamanouchi. Thus, the lemma is proved.

Proof of Theorem 1.1.

Let $\pi \in S_n$ . The explicit bijection $\varphi :\operatorname {\mathrm {PD}}^{red}(\pi )\rightarrow \operatorname {\mathrm {BPD}}^{red}(\pi )$ of [11] discussed in Section 2.6 is weight preserving; in particular, for $D\in \operatorname {\mathrm {PD}}^{red}(\pi )$ , the number of cross-tiles in row k equals the number of blank tiles in row k of $\varphi (D)$ , so $\operatorname {\mathrm {wt}}(D)=\operatorname {\mathrm {wt}}(\varphi (D))$ . By Theorem 3.3, TSSCPP are characterized as the set of pseudo-Yamanouchi pipe dreams in $\operatorname {\mathrm {PD}}(n)$ , and the weight is preserved in this bijection. Thus, whenever such pipe dreams are reduced, $\varphi $ produces a BPD with the same weight, which is in bijection with an ASM of the same weight. Thus, we have a weight-preserving injection $\varphi :\operatorname {\mathrm {TSSCPP}}^{red}(\pi )\hookrightarrow \operatorname {\mathrm {ASM}}^{red}(\pi )$ given by transforming the TSSCPP to its corresponding reduced pipe dream as in Theorem 3.3, mapping it to a reduced BPD using $\varphi $ and then transforming to an ASM using the bijection described in Section 2.4.

Suppose $\pi $ avoids $1432$ . Then by Lemma 4.3, all pipe dreams in $\operatorname {\mathrm {PD}}^{red}(\pi )$ are pseudo-Yamanouchi, so $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ is in bijection with $\operatorname {\mathrm {PD}}^{red}(\pi )$ . So the above injection is a bijection between $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ and $\operatorname {\mathrm {ASM}}^{red}(\pi )$ .

5 A poset-preserving bijection in the $2143$ - and $1432$ -avoiding case

In this section, we study posets constructed using simple slides on pipe dreams and simple droops on bumpless pipe dreams. We use this understanding to construct a bijection between $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ and $\operatorname {\mathrm {ASM}}(\pi )$ that preserves their poset structure in the case that $\pi $ avoids both $1432$ and $2143$ . Note that this bijection is not, in general, the same as the bijection $\varphi $ used in Theorem 1.1; see Remark 5.11. Note also that when $\pi $ avoids $2143$ , $\operatorname {\mathrm {ASM}}^{red}(\pi )=\operatorname {\mathrm {ASM}}(\pi )$ since all BPD that avoid $2143$ are reduced; see Lemma 5.3 below.

We use simple droops to define a poset on BPD. The Rothe BPD of $\pi $ is the BPD corresponding to the permutation matrix of $\pi $ . We will also refer to the Rothe BPD as the Rothe diagram of $\pi $ . Note that the connected regions of blank tiles of a Rothe diagram are all partition shaped.

Definition 5.1. Given $\pi \in S_n$ , let $\operatorname {{\mathrm {Droop}}}(\pi )$ denote the poset constructed from applying simple droops in all possible ways to the Rothe BPD of $\pi $ . The Rothe BPD is the bottom element of the poset and each simple droop moves up in the poset.

Note that this construction also induces a poset on the corresponding ASM by the simple bijection between BPD and ASM.

Definition 5.2. The set of essential boxes of a permutation $\pi $ is the set $\operatorname {\mathrm {ess}}(\pi ):=\{(i,j):\pi (j)>i, \pi ^{-1}(i)>j, \pi (j+1)\le i, \pi ^{-1}(i+1)\le j\}$ . In other words, $\operatorname {\mathrm {ess}}(\pi )$ consists of the southeast (SE)-most corners in the connected regions of blank tiles of the Rothe diagram of $\pi $ . Define the dominant region of Rothe diagram to be the connected region of blank tiles containing $(1,1)$ . Note that the dominant region might be empty.

The following statement is found in [21].

Lemma 5.3 [21, Lemma 7.2, Lemma 7.4 (2)].

If $\pi \in S_n$ avoids $2143$ , then any $D\in \operatorname {\mathrm {BPD}}(\pi )$ is reduced, and any two bumpless pipe dreams of $\pi $ are connected by simple droops.

This yields the following corollary.

Corollary 5.4. If $\pi \in S_n$ avoids $2143$ , the elements of $\operatorname {{\mathrm {Droop}}}(\pi )$ are all of $\operatorname {\mathrm {BPD}}(\pi )$ .

We define a similar poset for pipe dreams, using the simple slides of Section 2.5.

Definition 5.5. Given $\pi \in S_n$ , let $\operatorname {{\mathrm {Slide}}}(\pi )$ denote the poset constructed from applying simple slides to the bottom pipe dream in all possible ways. The bottom pipe dream is the bottom element of this poset, and each simple slide moves up in the poset.

We have the following, as a corollary of the result of Gao we stated as Theorem 4.1.

Corollary 5.6. If $\pi \in S_n$ avoids $1432$ , the elements of $\operatorname {{\mathrm {Slide}}}(\pi )$ are all of $\operatorname {\mathrm {PD}}^{red}(\pi )$ .

Figure 6 The Rothe BPD of a Grassmannian permutation is determined by blank tiles satisfying conditions (a)–(d) of Lemma 5.8. Transposing the diagrams, we get the analogous statements for inverse Grassmannians.

An important class of permutations are the Grassmannian permutations, which are defined as the permutations with at most one descent. Grassmannian permutations necessarily avoid both $2143$ and $1432$ since these patterns each have two descents. Inverse-Grassmannian permutations are permutations whose inverse is Grassmannian. These also avoid both $2143$ and $1432$ since these patterns are their own inverses.

We now relate $\operatorname {{\mathrm {Droop}}}(\pi )$ and $\operatorname {{\mathrm {Slide}}}(\pi )$ in the cases that $\pi $ is inverse-Grassmannian or Grassmannian. We will need the following lemmas, the first of which is also due to Weigandt.

Lemma 5.7 [21, Lemma 7.4 (1)].

If $\pi $ avoids $2143$ , all bumpless pipe dreams in $\operatorname {\mathrm {BPD}}(\pi )$ are uniquely determined by the locations of the blank tiles.

We remark that the same paper shows $1432$ -avoiding bumpless pipe dreams are in bijection with flagged tableaux constructed by filling the blank tiles with numbers [21, Theorem 1.6].

Lemma 5.8. The blank tiles in the Rothe BPD of a Grassmannian permutation have the following characterizing properties:

1. (a) Each connected region of blank tiles is a rectangular block.

2. (b) The essential boxes lie in the same row.

3. (c) The northwest (NW)-most blank tile of the leftmost rectangular block is on the diagonal.

4. (d) If $B_1$ and $B_2$ are two consecutive blocks and the horizontal distance between them is d, then the height of $B_1$ is d more than the width of $B_2$ .

Furthermore, if a set of blank tiles satisfy the properties above, this set uniquely determines the Rothe BPD of a Grassmannian permutation. If we replace (c) and (d) with the following

1. (b^′) The essential boxes lie in the same column.

2. (d^′) If $B_1$ and $B_2$ are two consecutive blocks and the vertical distance between them is d, then the width of $B_1$ is d more than the width of $B_2$ ,

we get similar characterizing properties for the inverse-Grassmannian permutations.

Proof. We may consider the permutation as an element in $S_\infty $ and the BPDs to be unbounded in the east and south directions. The Rothe BPD of an inverse-Grassmannian permutation is the transpose of that of a Grassmanian permutation, so it suffices to argue for Grassmannian permutations. It is easy to see the set of blank tiles of the Rothe BPD for a Grassmannian permutation satisfies properties (a)–(d). Given a set of blank tiles satisfying (a)–(d), we may construct a Rothe BPD by iteratively placing a tile at the NW-most undetermined position, and extending to the east by a horizontal ray and to the south by a vertical ray. The properties (a)–(d) guarantee that this is always possible; see Figure 6.

We are now ready to show a poset isomorphism between BPD and reduced PD in the inverse-Grassmannian case.

Theorem 5.9. If $\pi \in S_n$ is inverse-Grassmannian, there is an explicit weight-preserving bijection between $\operatorname {\mathrm {BPD}}(\pi )$ and $\operatorname {\mathrm {PD}}^{red}(\pi )$ such that $\operatorname {{\mathrm {Droop}}}(\pi ) \cong \operatorname {{\mathrm {Slide}}}(\pi )$ .

Figure 7 A weight-preserving and poset-preserving bijection between $\operatorname {\mathrm {BPD}}(14253)$ and $\operatorname {\mathrm {PD}}(14253)$ . Note that $14253$ is inverse Grassmannian and avoids both $1432$ and $2143$ .

Proof. Suppose $\pi \in S_n$ is inverse Grassmannian. By Lemma 5.7, since $\pi $ avoids $2143$ , the blank tiles of the BPD completely determine it. The map on the Rothe $\operatorname {\mathrm {BPD}}$ of $\pi $ that left justifies all the blank tiles and turns them into crosses results in the bottom (permutation) pipe dream of $\pi $ [3]. By Lemma 5.8, the blank tiles in the Rothe BPD of $\pi $ are disconnected rectangular blocks that are aligned on the right. When they are left justified to create the bottom pipe dream, they become mirror-image rectangular blocks aligned on the left. Furthermore, the NW-most blank tile in the Rothe $\operatorname {\mathrm {BPD}}$ is on the diagonal. The number of simple droops that may be applied to this blank tile then equals the number of simple slides that may be applied to the rightmost cross in this row of the bottom pipe dream. Moreover, the simple droop moves of $\operatorname {{\mathrm {Droop}}}(\pi )$ correspond exactly to the simple slides of $\operatorname {{\mathrm {Slide}}}(\pi )$ . Thus, $\operatorname {{\mathrm {Droop}}}(\pi ) \cong \operatorname {{\mathrm {Slide}}}(\pi )$ . By construction, the number of blank tiles in row k of a BPD in $\operatorname {{\mathrm {Droop}}}(\pi )$ corresponds to the number of cross-tiles in row k of the corresponding PD, so this weight is preserved. See Figure 7 for an example.

The following is a direct application of Theorem 5.9 to ASM and TSSCPP.

Corollary 5.10. If $\pi \in S_n$ is inverse Grassmannian, there is an explicit weight-preserving bijection between $\operatorname {\mathrm {ASM}}(\pi )$ and $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ such that $\operatorname {{\mathrm {Droop}}}(\pi ) \cong \operatorname {{\mathrm {Slide}}}(\pi )$ .

Remark 5.11. For crystal-theoretic reasons, the bijection of Corollary 5.10 coincides with the bijection $\varphi $ of Theorem 1.1, though this will not be true for the subsequent corollaries of this section.

We have a similar result for Grassmannian permutations, but the poset isomorphism is with the dual poset $\operatorname {{\mathrm {Slide}}}(\pi )^*$ (all order relations reversed). Note that in the case that $\pi $ avoids 1432, by Theorem 4.1, $\operatorname {{\mathrm {Slide}}}(\pi )$ has a unique maximal element, the pipe dream in which all the crosses are top justified; this is called the top pipe dream. Thus, $\operatorname {{\mathrm {Slide}}}(\pi )^*$ has the top pipe dream as its unique minimal element.

We now show a dual poset isomorphism between BPD and reduced PD in the Grassmannian case. Note that the transpose of a Grassmannian permutation is inverse Grassmannian, so Grassmannian permutations satisfy the transpose of the description in Theorem 5.9.

Theorem 5.12. If $\pi \in S_n$ is Grassmannian, there is an explicit bijection between $\operatorname {\mathrm {BPD}}(\pi )$ and $\operatorname {\mathrm {PD}}^{red}(\pi )$ such that $\operatorname {{\mathrm {Droop}}}(\pi ) \cong \operatorname {{\mathrm {Slide}}}(\pi )^*$ .

Proof. Suppose $\pi \in S_n$ is Grassmannian. By Lemma 5.7, since $\pi $ avoids $2143$ , the blank tiles of the BPD completely determine it. The map on the Rothe $\operatorname {\mathrm {BPD}}$ of $\pi $ that top justifies all the blank tiles and turns them into crosses results in the top pipe dream of $\pi $ . This can be seen by transposing the construction that left justifies blank tiles of inverse-Grassmannian Rothe BPDs as described in the proof of Theorem 5.9. By Lemma 5.8, the blank tiles in the Rothe BPD of $\pi $ are disconnected rectangular blocks that are aligned on the bottom. When they are top justified to create the top pipe dream, they become mirror-image rectangular blocks aligned on the top. Furthermore, the NW-most blank tile in the Rothe $\operatorname {\mathrm {BPD}}$ is on the diagonal. The number of simple droops that may be applied to this blank tile then equals the number of inverse simple slides that may be applied to the lowest cross in this column of the top pipe dream. Moreover, the simple droop moves of $\operatorname {{\mathrm {Droop}}}(\pi )$ correspond exactly to the inverse simple slides of $\operatorname {{\mathrm {Slide}}}(\pi )$ . Thus, $\operatorname {{\mathrm {Droop}}}(\pi ) \cong \operatorname {{\mathrm {Slide}}}(\pi )^*$ .

Remark 5.13. Note that by construction of this poset isomorphism, the number of blank tiles in row k of a BPD in $\operatorname {{\mathrm {Droop}}}(\pi )$ corresponds to the number of cross-tiles row $n-k+1$ of the corresponding PD, so this weight is reversed instead of preserved.

The corollary below follows immediately from Theorem 5.12.

Corollary 5.14. If $\pi \in S_n$ is Grassmannian, there is an explicit bijection between $\operatorname {\mathrm {ASM}}(\pi )$ and $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ such that $\operatorname {{\mathrm {Droop}}}(\pi ) \cong \operatorname {{\mathrm {Slide}}}(\pi )^*$ .

Remark 5.15. One may wonder why we use the dual poset in this theorem/corollary when many small examples, including that of Figure 7, seem to indicate that these posets may be self-dual. An example of a Grassmannian permutation $\pi $ for which $\operatorname {{\mathrm {Slide}}}(\pi )\neq \operatorname {{\mathrm {Slide}}}(\pi )^*$ is $\pi =146235$ .

Now, we generalize these correspondences to define a poset on $\operatorname {\mathrm {PD}}(\pi )$ in the case that $\pi $ avoids both $1,432$ and $2,143$ that is isomorphic to $\operatorname {{\mathrm {Droop}}}(\pi )$ . This will yield a poset-preserving bijection between the corresponding TSSCPP and ASM. First, we characterize features of these BPD in the lemmas below.

The following statement is well known. We include a short proof.

Lemma 5.16. If $\pi $ is $2143$ -avoiding, then essential boxes of the Rothe diagram of $\pi $ run northeast to southwest. Namely, it is impossible that $(i_1,j_1), (i_2,j_2)\in \operatorname {\mathrm {ess}}(\pi )$ such that $i_1<i_2$ and $j_1<j_2$ .

Proof. Let $\pi $ be a permutation, and suppose $(i_1,j_1)$ and $(i_2,j_2)$ are two essential boxes of $\pi $ . Suppose $i_1<i_2$ and $j_1<j_2$ . Since $(i_1,j_1)\in \operatorname {\mathrm {ess}}(\pi )$ , we have $\pi ^{-1}(j_1+1)\le i_1$ and $\pi (i_1+1)\le j_1$ . Since $(i_2,j_2)\in \operatorname {\mathrm {ess}}(\pi )$ , there exist $i_1+1<a\le i_2$ such that $\pi (a)>j_2$ and $j_1+1<b\le j_2$ such that $\pi ^{-1}(b)>i_2$ . We then have $\pi ^{-1}(j_1+1)<i_1+1<a<\pi ^{-1}(b)$ , where $\pi (i_1+1)<j_1+1<b<\pi (a)$ , so $\pi $ must be 2,143-containing.

Lemma 5.17. If $\pi $ is $1432$ -avoiding, the Rothe diagram of $\pi $ satisfies the following properties:

1. (a) The partition shapes formed by the blank region must all be rectangles, except for the dominant region.

2. (b) Let $B_1$ and $B_2$ be two nondominant connected regions of blank tiles with essential boxes $(i_1,j_1)$ and $(i_2,j_2)$ . If $B_1$ and $B_2$ both contain tiles in some row r, then $i_1=i_2$ . If $B_1$ and $B_2$ both contain tiles in some column j, then $j_1=j_2.$

Proof. For (a), suppose to the contrary that there is a nonrectangular partition that is not dominant. Let $(a,b)$ be its NW corner and $(i_1,j_1)$ , $(i_2,j_2)$ with $i_1<i_2$ and $j_1>j_2$ SE corners of this partition with no other SE corners in between. Note that $a>1$ . Let $(x,y)$ be the unique outer NW corner SW of $(i_1,j_1)$ and northeast (NE) of $(i_2,j_2)$ . It must be the case that $\pi (x)=y$ . Then $\pi (a-1)<b$ , $\pi (i_1)>j_1$ and $\pi ^{-1}(j_2)>i_2$ . Therefore, $a-1<i_1<x<\pi ^{-1}(j_2)$ and $\pi (a-1), \pi (i_1), \pi (x), j_2$ gives the pattern 1432, contradicting our assumption on $\pi $ .

For (b), we show the row statement and the column statement is similar. It suffices to consider the case when $B_1$ and $B_2$ are adjacent and $j_1<j_2$ . Now, suppose $i_1\neq i_2$ . Since $B_1$ and $B_2$ both contain tiles in some row r, we must have $i_1>i_2$ . Let $(a,b)$ be the NW corner of $B_1$ , then $\pi (a-1)<b\le j_1$ . Since $(i_2,j_2)\in \operatorname {\mathrm {ess}}(\pi )$ , $\pi (i_2)>j_2$ . Note also that $j_1<\pi (i_1)\le j_2$ . Finally, $\pi ^{-1}(b)>i_1$ . We then have $a-1<i_2<i_1<\pi ^{-1}(b)$ and $\pi (a-1)<b<\pi (i_1)<\pi (i_2)$ which gives the pattern 1,432.

Lemma 5.18. Suppose $\pi $ is $1432$ - and $2143$ -avoiding. If $(i,j_1),(i,j_2)\in \operatorname {\mathrm {ess}}(\pi )$ , $j_1<j_2$ and $(i,j_1)$ is not in the dominant region, then $(i',j_1)\not \in \operatorname {\mathrm {ess}}(\pi )$ for any $i'>i$ . Similarly, if $(i_1,j), (i_2,j)\in \operatorname {\mathrm {ess}}(\pi )$ , $i_1<i_2$ and $(i_1,j)$ is not in the dominant region, then $(i_1,j')\not \in \operatorname {\mathrm {ess}}(\pi )$ for any $j'>j$ .

Proof. Suppose $(i_1,j_1),(i_1,j_2),(i_2,j_1)\in \operatorname {\mathrm {ess}}(\pi )$ with $i_1<i_2$ and $j_1<j_2$ , and $(i_1,j_1)$ is not in the dominant region. Suppose B, $B_1$ , $B_2$ are the blank regions containing $(i_1,j_1)$ , $(i_1,j_2)$ and $(i_2,j_1)$ , respectively. Suppose $(a_1,b)$ is the NW corner of B and $a_2$ is the row index of the topmost row in $B_2$ . Then $\pi (a-1)<b\le j_1$ , $\pi (i_1)>j_2$ , and $\pi ^{-1}(j_1)>i_2$ . Since the essential boxes of 2143-avoiding permutations run NE to SW by Lemma 5.16, there can be no blank tiles strictly SE of $(i_1,j_1)$ , and therefore $j_1<\pi (a_2)\le j_2$ . We then have $a-1<i_1<a_2<\pi ^{-1}(j_1)$ and $\pi (a-1)<j_1<\pi (a_2)<\pi (i_2)$ giving the pattern 1432.

Definition-Lemma 5.19. If $\pi \in S_n$ is $2143$ - and $1432$ -avoiding, the Rothe $\operatorname {\mathrm {BPD}}$ can be partitioned into a dominant partition of empty squares in the NW corner, a partition shape of fixed pipes in the SE corner, and disjoint blocks containing nonintersecting pipes corresponding to Grassmannian and inverse-Grassmannian permutations. Call this the block-decomposition of $\pi $ .

Proof. By Lemmas 5.17 and 5.18, the set of essential boxes outside of the dominant region can be partitioned into $E_1,\cdots , E_m$ according to whether they lie on the same row or column. In particular, if $e_1,e_2\in E_i$ for some i, then either $e_1$ and $e_2$ are in the same row, or they are in the same column. If $E_i$ contain essential boxes in the same row r, let c be the smallest column index such that $(r,c)$ is not in the dominant region. Let $r'<r$ be the smallest row index such that $(r',c)$ is not in the dominant region. Let l be the sum of the widths of the rectangular blocks of blank tiles with essential boxes in $E_i$ . Then the rectangular region with $(r,c)$ as the SW corner of height $r-r'+1$ and width $l+r-r'+1$ consist of $r-r'+1$ nonintersecting pipes and agree with the top $r-r'+1$ rows of the Rothe BPD of a Grassmannian permutation by Lemma 5.8. Transposing this construction we get a rectangular region of inverse-Grassmannian permutation. The rest of the Rothe diagram contains fixed pipes, as there are no more blank tiles.

Theorem 5.20. Suppose $\pi \in S_n$ avoids both $2143$ and $1432$ . Let $\sigma _1,\sigma _2,\ldots ,\sigma _k$ be the inverse-Grassmannian permutations in the block decomposition of $\pi $ and $\tau _1,\tau _2,\ldots ,\tau _{\ell }$ the Grassmannian permutations in the block decomposition of $\pi $ . There is an explicit bijection between $\operatorname {\mathrm {BPD}}(\pi )$ and $\operatorname {\mathrm {PD}}^{red}(\pi )$ such that

$$\begin{align*}\operatorname{{\mathrm{Droop}}}(\pi) \cong \operatorname{{\mathrm{Slide}}}(\sigma_1)\times \operatorname{{\mathrm{Slide}}}(\sigma_2)\times \cdots\times \operatorname{{\mathrm{Slide}}}(\sigma_k)\times \operatorname{{\mathrm{Slide}}}(\tau_1)^*\times \operatorname{{\mathrm{Slide}}}(\tau_2)^*\times \cdots\times \operatorname{{\mathrm{Slide}}}(\tau_{\ell})^*.\end{align*}$$

Proof. By Lemma 5.19, the Rothe diagram of such a permutation is block Grassmannian and inverse Grassmannian. So we begin by mapping the Rothe diagram to a PD block-by-block. For the Grassmannian blocks, we map to the top pipe dream, and for the inverse-Grassmannian blocks, we map to the bottom pipe dream. Then from Theorems 5.9 and 5.12, the posets for each block are isomorphic or dual isomorphic. So we have the stated poset isomorphism.

The corollary below follows immediately.

Corollary 5.21. If $\pi \in S_n$ avoids both $2143$ and $1432$ , there is an explicit bijection $\psi $ between $\operatorname {\mathrm {ASM}}(\pi )$ and $\operatorname {\mathrm {TSSCPP}}^{red}(\pi )$ such that

$$\begin{align*}\operatorname{{\mathrm{Droop}}}(\pi) \cong \operatorname{{\mathrm{Slide}}}(\sigma_1)\times \operatorname{{\mathrm{Slide}}}(\sigma_2)\times \cdots\times \operatorname{{\mathrm{Slide}}}(\sigma_k)\times \operatorname{{\mathrm{Slide}}}(\tau_1)^*\times \operatorname{{\mathrm{Slide}}}(\tau_2)^*\times \cdots\times \operatorname{{\mathrm{Slide}}}(\tau_{\ell})^*,\end{align*}$$

where $\sigma _1,\sigma _2,\ldots ,\sigma _k$ are the inverse-Grassmannian permutations and $\tau _1,\tau _2,\ldots ,\tau _{\ell }$ the Grassmannian permutations in the block decomposition of $\pi $ .

Example 5.22. In Figure 8, we show an example of the Rothe BPD for a 2143- and 1432-avoiding permutation $\pi $ and its image under the poset-preserving bijection $\psi $ . The dominant partition in the upper left corner of each diagram is $(6,6,6,5,4)$ . The block decomposition of $\pi $ (from Definition-Lemma 5.19) consists of the Grassmannian permutation $\sigma =146235$ (shown in the upper right of each diagram) and the inverse-Grassmannian permutation $\tau =142563$ (shown in the lower left of each diagram).

Figure 8 Example of an Rothe BPD for a 2143- and 1432-avoiding permutation and its image under the poset-preserving bijection $\psi $ .

Remark 5.23. In [9], Fan and Guo give a formula with set-valued Rothe tableaux for Grothendieck polynomials indexed by 1432-avoiding permutations, which when restricted to the reduced case gives a formula for Schubert polynomials. It is not hard to see that their (set-valued) Rothe tableaux are in direct bijection with pipe dreams. In a similar spirit, Weigandt [21] gives a direct bijection between vexillary bumpless pipe dreams and flagged (set-valued) tableaux. It is possible to combine these tools in the $2143$ - and $1432$ -avoiding case to obtain a bijection between pipe dreams and bumpless pipe dreams via tableaux. Such a bijection agrees with the Gao–Huang bijection [11] and therefore is different from our poset-preserving bijection.

6 Concluding remarks

We conclude the paper by discussing the progress made thus far on the ASM-TSSCPP bijection problem and an outlook on and challenges to further progress. Table 1 below shows the numbers up to $n=7$ (computed using SageMath [17]) of ASM and TSSCPP that correspond using the theorems of this paper (Columns 3, 6, 7) as well as the results of [20, 1, 19, 7, 5] (Columns 2, 4, 5).

• • Column 2 is given by $n!$ , as this counts the permutation case bijection of [20].

• • Column 3 gives those matched under the poset-preserving $1432$ - and $2143$ -avoiding bijection of the present paper (Corollary 5.21).

• • Column 4 gives the number of ASM and TSSCPP matched in the bijection of [1, Theorem 4], which concerns the case that the monotone triangle associated to the ASM is gapless; this is the same set as the intersection discussed in [19, Section 7]. Remark 6.1 below explains the connection to pattern avoidance.

• • Column 5 gives the number matched in the bijections of [7, 5], which both concern the case of at most two nontrivial diagonals in the monotone triangle.

• • Column 6 gives the number matched in the weight-preserving $1432$ -avoiding bijection of the present paper (Theorem 1.1).

• • Column 7 gives the number matched in the weight-preserving injection of Theorem 1.1 on all TSSCPP whose pipe dreams are reduced.

• • Column 8 gives the total number of ASM, for comparison.

Table 1 The number of ASM and TSSCPP in correspondence via the various results of this paper and as compared to other subset bijections. The column headings in bold represent results from this paper.

One may ask whether any of these bijections include any of the other partial bijections. As noted earlier, the weight-preserving injection of Theorem 1.1 (Column $7$ ) extends the permutation case bijection of [20] (Column $2$ ). Also, the subsets addressed in this paper are proper subsets of each other (Columns 3, 6, 7). But it is useful to note that the subset of ASM included in other bijections discussed here may not be a proper subset of the ASM included in Theorem 1.1. In particular, the one ASM with $n=4$ whose BPD is nonreduced (pictured in Figure 9, upper right) has monotone triangle with only two nontrivial diagonals. Thus, it is included in the bijection of Column 5 [7, 5], but not in Theorem 1.1 (Column 7).

Figure 9 Challenges for the remaining unmatched TSSCPP pipe dreams and bumpless pipe dreams.

Remark 6.1. Pattern avoidance is discussed in [1], in the sense that the bijection of Column $4$ [1, Theorem 4] includes all permutations that avoid the pattern $312$ , using the conventions of that paper. In the conventions of the current paper, this corresponds to the set $\{\operatorname {\mathrm {ASM}}(\pi ) \ | \ \pi \mbox { avoids } 213\}$ , the ASM whose associated permutation $\pi $ avoids the pattern $213$ . (A gapless monotone triangle is obtained from such an ASM A as follows: The ith row consists of the column indices whose partial sum from the bottom row to row $(n-i+1)$ of A equals $1$ .) If a permutation avoids $213$ , it necessarily avoids $2143$ , but it might not avoid $1432$ . Table 1 shows that for small n, the cardinality of $\{\operatorname {\mathrm {ASM}}(\pi ) \ | \ \pi \mbox { avoids } 213\}$ is smaller than the cardinality of $\{\operatorname {\mathrm {ASM}}(\pi ) \ | \ \pi \mbox { avoids } 1432 \mbox { and } 2143\}$ , but for larger values of n in the table, this comparison is reversed.

One may ask whether it is possible to extend the bijection of Theorem 1.1 beyond $1432$ -avoiding permutations and/or remove the reducedness restrictions. There are some challenges. In the case of $n=4$ , $40$ pseudo-Yamanouchi pipe dreams are reduced, so all the corresponding TSSCPP are mapped to reduced BPD and therefore to ASM. There are only two remaining TSSCPPs, shown in the left column of Figure 9. There is one remaining reduced pipe dream, shown in the bottom middle of Figure 9, which maps by $\varphi $ to the BPD on the bottom right. Comparing this reduced pipe dream with the two remaining TSSCPP pipe dreams, we see it differs from the one with three crosses by moving the top cross to the right, creating a nonreduced pipe dream. In general, the set of reduced pipe dreams for a fixed permutation are connected by $(n\times 2)$ –ladder moves and $(2\times n)$ –chute moves [3], and these moves do not always preserve the pseudo-Yamanouchi property when $n>2$ .

In the forthcoming work of Shimozono, Yu and the first author, a weight-preserving bijection between the set of all $2^{\binom {n}{2}}$ pipe dreams in $\operatorname {\mathrm {PD}}(n)$ and the set of all marked bumpless pipe dreams (a marked BPD is a BPD whose -tiles admit a binary marking) of size n, which generalizes the bijection in [11]. Under this bijection, the BPD on the top right of Figure 9 is mapped to the PD on the top middle. Notice that the one remaining TSSCPP PD on the top left has one more , so a bijection that preserves this weight is no longer possible.