]Lenart's bijection via bumpless pipe dreams
A. Gregory]Adam Gregory
[AG]Department of Mathematics, University of Florida, Gainesville, FL 32601

Z. Hamaker]Zachary Hamaker
[ZH]Department of Mathematics, University of Florida, Gainesville, FL 32601

Pipe dreams and bumpless pipe dreams for vexillary permutations are each known to be in bijection with certain semistandard tableaux via maps due to Lenart and Weigandt, respectively.
Recently, Gao and Huang have defined a bijection between the former two sets.
In this note we show for vexillary permutations that the Gao–Huang bijection preserves the associated tableaux, giving a new proof of Lenart's result.
Our methods extend to give a recording tableau for any bumpless pipe dream.

§ INTRODUCTION

Schubert polynomials are fundamental objects in algebraic combinatorics and enumerative algebraic geometry.
They have several combinatorial formulas, most notably the Billey-Jockusch-Stanley pipe dream formula [1, 3].
Schubert polynomials associated to vexillary permutations are flagged Schur functions, which have a formula in terms of flagged tableaux [21].
As part of an effort to extend this type of formula to all Schubert polynomials, Lenart described a bijection from pipe dreams to flagged tableaux <cit.>.
Lenart's map relies on Edelman-Greene insertion [4], and he does not give a proof, remarking `the proof is somewhat technical, and therefore we decided to omit it.'
A special case of Lenart's map appears as <cit.>.

Recently Lam, Lee and Shimozono introduced a new combinatorial model for Schubert polynomials called the bumpless pipe dream formula [15].
Building on work of Kreiman [14] and Knutson-Miller-Yong [13], Weigandt observed that bumpless pipe dreams for vexillary permutations are manifestly in bijection with flagged tableaux <cit.>.
Later, Gao and Huang gave a bijection between bumpless pipe dreams and pipe dreams [7].
By composing these maps, one obtains a new bijection from pipe dreams to flagged tableaux.
See Figure <ref> for an example of these maps.

Our main result is:

The composition of the Weigandt and Gao-Huang bijections is equal to Lenart's bijection.

As a consequence, we obtain the first explicit proof of Lenart's bijection, avoiding many of the technicalities required in a direct approach at the expense of drawing on a larger body of prior work.
To prove Theorem <ref>, we first demonstrate the Grassmannian case (see Theorem <ref>).
We then use combinatorial recurrences on pipe dreams [2, 18] and bumpless pipe dreams [9] to extend this to the vexillary case.
In doing so, we make critical use of the `canonical' nature of the Gao-Huang bijection and a result of the second author and Young [8].
From this perspective, our work extends the Little bijection [18] to give an intrinsic description of `recording' tableaux for bumpless pipe dreams (see Section <ref>).
A direct generalization of this map will appear in forthcoming work by Huang, Shimozono and Yu [23].

In the second section, we introduce the objects studied in this paper and their properties: permutations and reduced words, flagged tableaux, reduced compatible sequences [3] and pipe dreams [1], bumpless pipe dreams [15, 22].
The third section describes properties of the various maps that we require: the Edelman-Greene correspondence [4] and Lenart's bijection [17], the Gao-Huang bijection between pipe dreams and bumpless pipe dreams [7],  the Little bijection [18], Huang's combinatorial realization of Monk's formula [9] (precise definitions appear in the appendix).
We prove our main results in the fourth section.
The fifth section discusses an extension of [9] and some forthcoming work.

We thank Joshua Arroyo, Daoji Huang and Tianyi Yu for helpful conversations.
We are especially grateful to Hugh Dennin for sharing his code for bumpless pipe dreams and related maps and to Anna Weigandt for suggesting this problem.

§ OBJECTS

Let $[n] = \{1,2,\dots,n\}$.

§.§ Permutations

For our purposes, a permutation $w$ is a bijection of the positive integers so that $w(k) = k$ for all but finitely many $k$.
Let $S_\infty$ denote the set of all permutations.

The support of $w \in S_\infty$ is $\text{supp}(w) = \{k: w(k) \neq k \}$.
With these conventions, the usual symmetric group is $S_n = \{w \in S_\infty: \text{supp}(w) \subseteq [n]\}$.
For $w \in S_n$, we have the one-line notation $w = w(1) \ldots w(n)$.

Given integers $j > i \geq 1$, let $t_{ij}$ be the transposition of the integers $i$ and $j$.
Similarly, let $s_i = t_{i\:i+1}$ denote a simple transposition.
It is well-known that every $w \in S_\infty$ can be written as a product of simple transpositions.

For $w = s_{a_1} \dots s_{a_p}$ an expression of a minimal length, we call $\textbf{a} = (a_1,\dots,a_p)$ a reduced word for $w$.
Let $\text{Red}(w)$ denote the set of reduced words for $w$ and $\ell(w)$ be the length of a reduced word.

For $w \in S_\infty$, a descent is a value $k$ such that $w(k) > w(k+1)$.

A permutation $w$ is called Grassmannian if it has at most one descent.
A permutation $w$ is vexillary if for all $1 \leq i < j < k < \ell$, we do not have $w(j) < w(i) < w(\ell) < w(k)$.
Equivalently, vexillary permutations are those avoiding the pattern 2143.
Note every Grassmannian permutation is also vexillary.

The code of $w \in S_\infty$ is $c(w) = (c_1(w), \ldots, c_n(w))$ where

\[c_i(w) = |\{j : j > i \; \text{and} \; w(i) > w(j)\}|.
\]

The shape of $w$ is the integer partition $\lambda(w)$ obtained by rearranging $c(w)$ to be weakly decreasing.
For example, $c(1432) = (0,2,1,0)$ and so $\lambda(1432) = (2,1)$.

§.§ Diagrams and Tableaux

A diagram is a subset of $[n] \times [n]$. We use matrix coordinates for these arrays, so row indices increase from top-to-bottom and column indices increase from left-to-right.

The Rothe diagram of a permutation $w \in S_n$ is

\[
D_w = \{(i,w(j)) : i < j \; \text{and} \; w(i) > w(j) \}.
\]

The Young diagram of an integer partition $\lambda = (\lambda_1, \lambda_2, \ldots)$ given by

\[
Y_\lambda = \{(i,j) : 1 \leq j \leq \lambda_i\}.
\]

A Young tableau is a positive integer filling of a Young diagram.
It is semi-standard if its filling increases weakly across rows and strictly down columns.
The shape of a tableau is its underlying partition.
For $\lambda = (\lambda_1,\dots,\lambda_\ell)$ a partition, let $\text{SSYT}(\lambda)$ denote the set of semi-standard Young tableaux with shape $\lambda$.

Similarly, $\text{SSYT}_k(\lambda)$ is the subset of semi-standard tableaux with maximum entry ${\leq k}$.
More generally, for $\phi = (\phi_1, \ldots, \phi_\ell)$ positive integers,  define

\[
\text{SSYT}_\phi(\lambda) = \{T \in \text{SSYT}(\lambda): T_{i\lambda_i} \leq \phi_i \ \mbox{for}\ i \in [\ell]\}
\]

where $T_{ij}$ is the filling in $(i,j)$.
We call $\phi$ a flag and $\text{SSYT}_\phi(\lambda)$ the set of $\phi$-flagged semi-standard Young tableau of shape $\lambda$.
For example,

\[\text{SSYT}_{(2,3)}(2,1) = \left\{\ytableausetup{smalltableaux}
\begin{ytableau}
1 & 1 \\ 2
\end{ytableau}, \quad
\begin{ytableau}
1 & 1 \\ 3
\end{ytableau}, \quad
\begin{ytableau}
1 & 2 \\ 2
\end{ytableau}, \quad
\begin{ytableau}
1 & 2 \\ 3
\end{ytableau}, \quad
\begin{ytableau}
2 & 2 \\ 3
\end{ytableau}
\right\}.
\]

Each vexillary permutation has a flag $\phi(v) = (\phi_1, \ldots, \phi_m)$ associated to it in the following way.
Let $v$ be a vexillary permutation with Rothe diagram $D_v$ and shape $\lambda(v) = (\lambda_1, \ldots, \lambda_m)$.
Then $\phi_i$ is equal to the row index of the southeastern-most box in $D_v$ which lies in the same diagonal as $(i,\lambda_i)$.
If $v$ is Grassmannian with $\text{Des}(v) = \{k\}$ one can check that $\phi(v) = (k, \ldots, k)$.
For example, with $w = 35142$ we see $\text{code}(w) = (2,3,0,1,0)$ so that $\lambda(w) = (3,2,1)$.
Then $\phi(w) = (2,2,4)$:

\[
\begin{tikzpicture}[scale=0.4]
\node at (1,1) {\nowire};
\node at (0,3) {\nowire};
\node at (0,4) {\nowire};
\node at (1,3) {\nowire};
\node at (1,4) {\nowire};
\node at (3,3) {\nowire};
\draw[dashed] (-0.5,-0.5) -- (-0.5,4.5) -- (4.5,4.5) -- (4.5,-0.5) -- (-0.5,-0.5);
\end{tikzpicture} \quad
\begin{tikzpicture}[scale=0.4]
\node at (1,1) {\nowire};
\node at (0,3) {\nowire};
\node at (0,4) {\nowire};
\node at (1,3) {\nowire};
\node at (1,4) {\nowire};
\node at (3,3) {\nowire};
\draw[dashed] (-0.5,-0.5) -- (-0.5,4.5) -- (4.5,4.5) -- (4.5,-0.5) -- (-0.5,-0.5);
\draw[red] (-0.5,1.5) -- (0.5,1.5) -- (0.5,2.5) -- (1.5,2.5) -- (1.5,3.5) -- (2.5,3.5) -- (2.5,4.5) -- (-0.5,4.5) -- (-0.5,1.5);
\end{tikzpicture} \quad
\begin{tikzpicture}[scale=0.4]
\node at (1,1) {\shade};
\node at (0,2) {\shade};
\node at (0,3) {\nowire};
\node at (0,4) {\nowire};
\node at (1,3) {\shade};
\node at (1,4) {\nowire};
\node at (2,4) {\shade};
\node at (3,3) {\shade};
\node at (1,1) {4};
\node at (1,3) {2};
\node at (3,3) {2};

\draw[dashed] (-0.5,-0.5) -- (-0.5,4.5) -- (4.5,4.5) -- (4.5,-0.5) -- (-0.5,-0.5);
\draw[red] (-0.5,1.5) -- (0.5,1.5) -- (0.5,2.5) -- (1.5,2.5) -- (1.5,3.5) -- (2.5,3.5) -- (2.5,4.5) -- (-0.5,4.5) -- (-0.5,1.5);
\draw[->] (2.5,3.5) -- (2,4);
\draw[->] (0.5,1.5) -- (0,2);
\end{tikzpicture}
\]

For partitions $\mu$ and $\lambda$ say $\mu \subseteq \lambda$ if $Y_\mu \subseteq Y_\lambda$.
Given $\mu \subseteq \lambda$, the associated skew diagram is $Y_{\lambda /\mu} = Y_\lambda \setminus Y_\mu$.
A skew tableau of shape $\lambda / \mu$ is a filling of $Y_{\lambda /\mu}$ with positive integers.
For a tableau $T$ of shape $\lambda$ and $\mu \subseteq \lambda$, let $T/\mu$ be the skew tableau obtained by restricting $T$ to the skew diagram $Y_{\lambda / \mu}$.

Let $T$ be a skew tableau of shape $\lambda / \mu$.
An outer corner of $T$ is a rightmost box in some row of $Y_\lambda$.
An inner corner of $T$ is a rightmost box in some row of $Y_\mu$.
Jeu de taquin is an invertible process on skew tableaux that adds a distinguished inner corner and removes an outer corner according to the following sliding rule: starting with the inner corner, repeatedly compare the fillings to the right and below the empty tile and swap places with the smaller of the two, breaking ties by moving down and treating boxes outside the tableau as being filled with $\infty$.
To perform rectification on $T$, do jeu de taquin one at a time to every cell in $Y_\mu$.
Let $\text{rect}(T)$ denote the rectification of $T$.
See <cit.> for precise definitions of these maps.

Given a tableau $T$, let $\text{jdt}(T) = \text{rect}(T/(1))$.
For example, with

\[
T =
\begin{ytableau}
1 & 1 & 3 & 4 \\
2 & 4 & 4 & 5\\
3 & 5
\end{ytableau}\]

we compute (with $\bullet$ indicating the empty tile)

\[
\begin{ytableau}
\none[\bullet] & 1 & 3 & 4 \\
2 & 4 & 4 & 5\\
3 & 5
\end{ytableau} \rightarrow
\begin{ytableau}
1 & \none[\bullet] & 3 & 4 \\
2 & 4 & 4 & 5 \\
3 & 5
\end{ytableau}  \rightarrow
\begin{ytableau}
1 & 3 & \none[\bullet] & 4 \\
2 & 4 & 4 & 5 \\
3 & 5
\end{ytableau}  \rightarrow
\begin{ytableau}
1 & 3 & 4 & 4 \\
2 & 4 & \none[\bullet] & 5 \\
3 & 5
\end{ytableau}  \rightarrow
\begin{ytableau}
1 & 3 & 4 & 4 \\
2 & 4 & 5 & \none[\bullet] \\
3 & 5
\end{ytableau}
= \text{jdt}(T).
\]

Since jeu de taquin slides are invertible, we can invert $\text{jdt}(T)$ when we know the shape of $T$ and the filling removed from its top left corner.

§.§ Reduced Compatible Sequences and Pipe Dreams

The Billey-Jockusch-Stanley formula for Schubert polynomials is given in terms of certain biwords called reduced compatible sequences [3].

A reduced compatible sequence for a permutation $w$ is a biword $\binom{\mathbf{r}}{\mathbf{a}} = \binom{r_1, \ldots, r_\ell}{a_1, \ldots, a_\ell}$ such that

(i) $\mathbf{a}$ is a reduced word for $w$,

(ii) $r_i \leq r_{i+1}$ for each $1 \leq i \leq \ell$,

(iii) $r_i \leq a_i$ for each $1 \leq i \leq \ell$, and

(iv) $r_i < r_{i+1}$ whenever $a_i < a_{i+1}$.

In [1], Bergeron and Billey gave a diagrammatic representation of reduced compatible sequences that are now commonly known as pipe dreams.
For $n \geq 2$ let $\delta_n = (n-1,n-2,\ldots,2,1)$.

A (reduced) pipe dream is a filling of the staircase diagram $Y_{\delta_n}$ using the tiles

\[
\cross \quad \text{and} \quad \bump
\]

in such a way that $n$ pipes enter from the top and exit to the left without any pair of pipes crossing more than once.

\[
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\jay};

\node at (0,1) {\bump};
\node at (1,1) {\jay};

\node at (0,2) {\bump};
\node at (1,2) {\cross};
\node at (2,2) {\jay};

\node at (0,3) {\bump};
\node at (1,3) {\bump};
\node at (2,3) {\bump};
\node at (3,3) {\jay};

\node at (0,4) {\cross};
\node at (1,4) {\bump};
\node at (2,4) {\cross};
\node at (3,4) {\bump};
\node at (4,4) {\jay};

\draw[thick] (-0.5,-0.5) -- (-0.5,4.5) -- (4.5,4.5);

\node at (0,5) {1};
\node at (1,5) {2};
\node at (2,5) {3};
\node at (3,5) {4};
\node at (4,5) {5};

\node at (-1,4) {2};
\node at (-1,3) {1};
\node at (-1,2) {4};
\node at (-1,1) {5};
\node at (-1,0) {3};

\node at (2,-2) {Example};
\end{tikzpicture} \; \hspace{0.5in} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\jay};

\node at (0,1) {\bump};
\node at (1,1) {\jay};

\node at (0,2) {\bump};
\node at (1,2) {\cross};
\draw[red,thick] (1,2) circle (0.4);
\node at (2,2) {\jay};

\node at (0,3) {\bump};
\node at (1,3) {\bump};
\node at (2,3) {\cross};
\draw[red,thick] (2,3) circle (0.4);
\node at (3,3) {\jay};

\node at (0,4) {\bump};
\node at (1,4) {\bump};
\node at (2,4) {\cross};
\node at (3,4) {\bump};
\node at (4,4) {\jay};

\draw[thick] (-0.5,-0.5) -- (-0.5,4.5) -- (4.5,4.5);

\node at (0,5) {1};
\node at (1,5) {2};
\node at (2,5) {3};
\node at (3,5) {4};
\node at (4,5) {5};

\node at (-1,4) {1};
\node at (-1,3) {2};
\node at (-1,2) {4};
\node at (-1,1) {5};
\node at (-1,0) {3};

\node at (2,-2) {Non-example};
\end{tikzpicture}
\]

Pipes are labeled $1$ through $n$ from left-to-right across the top, and the order in which they exit from top-to-bottom gives the permutation of a pipe dream.
For $w \in S_\infty$, let $\text{PD}(w)$ denote the set of all pipe dreams whose permutation is $w$.

The correspondence between pipe dreams and reduced compatible sequences is as follows.
Given $P$ in $\text{PD}(w)$, map the locations $(i,j)$ of each $\inlinecross$-tile in $P$ to $\binom{i}{j+i-1}$ and concatenate these in the order of right-to-left and top-to-bottom.
For the inverse, the reduced compatible sequence $\binom{r_1, \ldots, r_\ell}{a_1, \ldots, a_\ell}$ maps to the pipe dream having $\inlinecross$-tiles in locations $(r_i, a_i - r_i + 1)$.

\[
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\jay};

\node at (0,1) {\cross};
\node at (1,1) {\jay};

\node at (0,2) {\cross};
\node at (1,2) {\cross};
\node at (2,2) {\jay};

\node at (0,3) {\bump};
\node at (1,3) {\bump};
\node at (2,3) {\bump};
\node at (3,3) {\jay};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5);

\node at (0,4) {1};
\node at (1,4) {2};
\node at (2,4) {3};
\node at (3,4) {4};

\node at (-1,3) {1};
\node at (-1,2) {4};
\node at (-1,1) {3};
\node at (-1,0) {2};

\node at (3,0) {$\binom{2,2,3}{3,2,3}$};
\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\jay};

\node at (0,1) {\cross};
\node at (1,1) {\jay};

\node at (0,2) {\cross};
\node at (1,2) {\bump};
\node at (2,2) {\jay};

\node at (0,3) {\bump};
\node at (1,3) {\bump};
\node at (2,3) {\cross};
\node at (3,3) {\jay};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5);

\node at (0,4) {1};
\node at (1,4) {2};
\node at (2,4) {3};
\node at (3,4) {4};

\node at (-1,3) {1};
\node at (-1,2) {4};
\node at (-1,1) {3};
\node at (-1,0) {2};

\node at (3,0) {$\binom{1,2,3}{3,2,3}$};
\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\jay};

\node at (0,1) {\bump};
\node at (1,1) {\jay};

\node at (0,2) {\cross};
\node at (1,2) {\cross};
\node at (2,2) {\jay};

\node at (0,3) {\bump};
\node at (1,3) {\cross};
\node at (2,3) {\bump};
\node at (3,3) {\jay};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5);

\node at (0,4) {1};
\node at (1,4) {2};
\node at (2,4) {3};
\node at (3,4) {4};

\node at (-1,3) {1};
\node at (-1,2) {4};
\node at (-1,1) {3};
\node at (-1,0) {2};

\node at (3,0) {$\binom{1,2,2}{2,3,2}$};
\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\jay};

\node at (0,1) {\cross};
\node at (1,1) {\jay};

\node at (0,2) {\bump};
\node at (1,2) {\bump};
\node at (2,2) {\jay};

\node at (0,3) {\bump};
\node at (1,3) {\cross};
\node at (2,3) {\cross};
\node at (3,3) {\jay};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5);

\node at (0,4) {1};
\node at (1,4) {2};
\node at (2,4) {3};
\node at (3,4) {4};

\node at (-1,3) {1};
\node at (-1,2) {4};
\node at (-1,1) {3};
\node at (-1,0) {2};

\node at (3,0) {$\binom{1,1,3}{3,2,3}$};
\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\jay};

\node at (0,1) {\bump};
\node at (1,1) {\jay};

\node at (0,2) {\bump};
\node at (1,2) {\cross};
\node at (2,2) {\jay};

\node at (0,3) {\bump};
\node at (1,3) {\cross};
\node at (2,3) {\cross};
\node at (3,3) {\jay};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5);

\node at (0,4) {1};
\node at (1,4) {2};
\node at (2,4) {3};
\node at (3,4) {4};

\node at (-1,3) {1};
\node at (-1,2) {4};
\node at (-1,1) {3};
\node at (-1,0) {2};

\node at (3,0) {$\binom{1,1,2}{3,2,3}$};
\end{tikzpicture}
\]

Due to this correspondence, we use pipe dreams and reduced compatible sequences interchangebly.

§.§ Bumpless Pipe Dreams

Recently, Lam, Lee and Shimozono gave a new diagrammatic formula for Schubert polynomials in terms of diagrams called bumpless pipe dreams [15].
As Weigandt observed [22], their formula is equivalent to a prior formula due to Lascoux [16].

A (reduced) bumpless pipe dream is a filling of an $n \times n$ grid using tiles from

\[
\nowire \quad \vwire \quad \hwire \quad \are \quad \jay \quad \cross
\]

in such a way that $n$ pipes enter from the bottom and exit to the right without any pair of pipes crossing more than once.

\[
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\vwire};
\node at (2,0) {\are};
\node at (3,0) {\cross};
\node at (4,0) {\cross};

\node at (0,1) {\vwire};
\node at (1,1) {\are};
\node at (2,1) {\jay};
\node at (3,1) {\vwire};
\node at (4,1) {\are};

\node at (0,2) {\are};
\node at (1,2) {\jay};
\node at (2,2) {\vwire};
\node at (3,2) {\are};
\node at (4,2) {\hwire};

\node at (0,3) {\nowire};
\node at (1,3) {\are};
\node at (2,3) {\cross};
\node at (3,3) {\hwire};
\node at (4,3) {\hwire};

\node at (0,4) {\nowire};
\node at (1,4) {\nowire};
\node at (2,4) {\are};
\node at (3,4) {\hwire};
\node at (4,4) {\hwire};

\draw[thick] (-0.5,-0.5) -- (-0.5,4.5) -- (4.5,4.5) -- (4.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};
\node at (4,-1) {5};

\node at (5,4) {2};
\node at (5,3) {1};
\node at (5,2) {4};
\node at (5,1) {5};
\node at (5,0) {3};

\node at (2,-2.5) {Example};
\end{tikzpicture} \; \hspace{0.5in} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\vwire};
\node at (2,0) {\are};
\node at (3,0) {\cross};
\node at (4,0) {\cross};

\node at (0,1) {\are};
\node at (1,1) {\cross};
\draw[red,thick] (1,1) circle (0.4);
\node at (2,1) {\jay};
\node at (3,1) {\vwire};
\node at (4,1) {\are};

\node at (0,2) {\nowire};
\node at (1,2) {\vwire};
\node at (2,2) {\vwire};
\node at (3,2) {\are};
\node at (4,2) {\hwire};

\node at (0,3) {\nowire};
\node at (1,3) {\are};
\node at (2,3) {\cross};
\draw[red,thick] (2,3) circle (0.4);
\node at (3,3) {\hwire};
\node at (4,3) {\hwire};

\node at (0,4) {\nowire};
\node at (1,4) {\nowire};
\node at (2,4) {\are};
\node at (3,4) {\hwire};
\node at (4,4) {\hwire};

\draw[thick] (-0.5,-0.5) -- (-0.5,4.5) -- (4.5,4.5) -- (4.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};
\node at (4,-1) {5};

\node at (5,4) {1};
\node at (5,3) {2};
\node at (5,2) {4};
\node at (5,1) {5};
\node at (5,0) {3};

\node at (2,-2.5) {Non-example};
\end{tikzpicture}
\]

The pipes are labeled $1$ to $n$ from left-to-right across the bottom, and the order in which they exit from top-to-bottom determines the permutation of a bumpless pipe dream.
Given $w \in S_\infty$, let $\text{BPD}(w)$ denote the set of all bumpless pipe dreams with permutation $w$.
Below are the elements of $\text{BPD}(1432)$:

\[
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\are};
\node at (2,0) {\cross};
\node at (3,0) {\cross};

\node at (0,1) {\vwire};
\node at (1,1) {\nowire};
\node at (2,1) {\are};
\node at (3,1) {\cross};

\node at (0,2) {\vwire};
\node at (1,2) {\nowire};
\node at (2,2) {\nowire};
\node at (3,2) {\are};

\node at (0,3) {\are};
\node at (1,3) {\hwire};
\node at (2,3) {\hwire};
\node at (3,3) {\hwire};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5) -- (3.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};

\node at (4,3) {1};
\node at (4,2) {4};
\node at (4,1) {3};
\node at (4,0) {2};

\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\are};
\node at (2,0) {\cross};
\node at (3,0) {\cross};

\node at (0,1) {\vwire};
\node at (1,1) {\nowire};
\node at (2,1) {\are};
\node at (3,1) {\cross};

\node at (0,2) {\are};
\node at (1,2) {\jay};
\node at (2,2) {\nowire};
\node at (3,2) {\are};

\node at (0,3) {\nowire};
\node at (1,3) {\are};
\node at (2,3) {\hwire};
\node at (3,3) {\hwire};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5) -- (3.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};

\node at (4,3) {1};
\node at (4,2) {4};
\node at (4,1) {3};
\node at (4,0) {2};

\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\are};
\node at (2,0) {\cross};
\node at (3,0) {\cross};

\node at (0,1) {\are};
\node at (1,1) {\jay};
\node at (2,1) {\are};
\node at (3,1) {\cross};

\node at (0,2) {\nowire};
\node at (1,2) {\vwire};
\node at (2,2) {\nowire};
\node at (3,2) {\are};

\node at (0,3) {\nowire};
\node at (1,3) {\are};
\node at (2,3) {\hwire};
\node at (3,3) {\hwire};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5) -- (3.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};

\node at (4,3) {1};
\node at (4,2) {4};
\node at (4,1) {3};
\node at (4,0) {2};

\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\are};
\node at (2,0) {\cross};
\node at (3,0) {\cross};

\node at (0,1) {\vwire};
\node at (1,1) {\nowire};
\node at (2,1) {\are};
\node at (3,1) {\cross};

\node at (0,2) {\are};
\node at (1,2) {\hwire};
\node at (2,2) {\jay};
\node at (3,2) {\are};

\node at (0,3) {\nowire};
\node at (1,3) {\nowire};
\node at (2,3) {\are};
\node at (3,3) {\hwire};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5) -- (3.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};

\node at (4,3) {1};
\node at (4,2) {4};
\node at (4,1) {3};
\node at (4,0) {2};

\end{tikzpicture} \;
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\are};
\node at (2,0) {\cross};
\node at (3,0) {\cross};

\node at (0,1) {\are};
\node at (1,1) {\jay};
\node at (2,1) {\are};
\node at (3,1) {\cross};

\node at (0,2) {\nowire};
\node at (1,2) {\are};
\node at (2,2) {\jay};
\node at (3,2) {\are};

\node at (0,3) {\nowire};
\node at (1,3) {\nowire};
\node at (2,3) {\are};
\node at (3,3) {\hwire};

\draw[thick] (-0.5,-0.5) -- (-0.5,3.5) -- (3.5,3.5) -- (3.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};

\node at (4,3) {1};
\node at (4,2) {4};
\node at (4,1) {3};
\node at (4,0) {2};

\end{tikzpicture}
\]

For $v$ vexillary, Weigandt  recently introduced a bijection [22]

\[
\gamma: \text{BPD}(v) \rightarrow \text{SSYT}_{\phi(v)}(\lambda(v)).
\]

The correspondence can be described as follows.
Given $B \in \text{BPD}(v)$, fill each $\inlinenowire$-tile with the number of pipes that are above it.
Next, ignore all pipes and slide each number-filled tile northwest along its main diagonal to create a partition in the upper-left corner.
This step is well-defined as $v$ is vexillary.
Lastly, increase the value of each filling by its row index, i.e., add $i$ to each filling in row $i$ for all rows.
For example, with $B \in \text{BPD}(12587634)$ as below, we compute $\gamma(B)$:

\[
\centering
\begin{tabular}{ccc}
\begin{tikzpicture}[scale=0.4]
\node at (-2,4) {$B = $};
\node at (0,0) {\vwire};
\node at (1,0) {\vwire};
\node at (2,0) {\vwire};
\node at (3,0) {\are};
\node at (4,0) {\cross};
\node at (5,0) {\cross};
\node at (6,0) {\cross};
\node at (7,0) {\cross};

\node at (0,1) {\vwire};
\node at (1,1) {\vwire};
\node at (2,1) {\are};
\node at (3,1) {\hwire};
\node at (4,1) {\cross};
\node at (5,1) {\cross};
\node at (6,1) {\cross};
\node at (7,1) {\cross};

\node at (0,2) {\vwire};
\node at (1,2) {\vwire};
\node at (2,2) {\nowire};
\node at (2,2) {2};
\node at (3,2) {\nowire};
\node at (3,2) {2};
\node at (4,2) {\vwire};
\node at (5,2) {\are};
\node at (6,2) {\cross};
\node at (7,2) {\cross};

\node at (0,3) {\vwire};
\node at (1,3) {\vwire};
\node at (2,3) {\nowire};
\node at (2,3) {2};
\node at (3,3) {\nowire};
\node at (3,3) {2};
\node at (4,3) {\are};
\node at (5,3) {\jay};
\node at (6,3) {\are};
\node at (7,3) {\cross};

\node at (0,4) {\vwire};
\node at (1,4) {\are};
\node at (2,4) {\hwire};
\node at (3,4) {\hwire};
\node at (4,4) {\jay};
\node at (5,4) {\are};
\node at (6,4) {\jay};
\node at (7,4) {\are};

\node at (0,5) {\vwire};
\node at (1,5) {\nowire};
\node at (1,5) {1};
\node at (2,5) {\nowire};
\node at (2,5) {1};
\node at (3,5) {\nowire};
\node at (3,5) {1};
\node at (4,5) {\vwire};
\node at (5,5) {\nowire};
\node at (5,5) {2};
\node at (6,5) {\are};
\node at (7,5) {\hwire};

\node at (0,6) {\are};
\node at (1,6) {\hwire};
\node at (2,6) {\jay};
\node at (3,6) {\nowire};
\node at (3,6) {1};
\node at (4,6) {\are};
\node at (5,6) {\hwire};
\node at (6,6) {\hwire};
\node at (7,6) {\hwire};

\node at (0,7) {\nowire};
\node at (0,7) {0};
\node at (1,7) {\nowire};
\node at (1,7) {0};
\node at (2,7) {\are};
\node at (3,7) {\hwire};
\node at (4,7) {\hwire};
\node at (5,7) {\hwire};
\node at (6,7) {\hwire};
\node at (7,7) {\hwire};

\draw (-0.5,-0.5) -- (-0.5,7.5) -- (7.5,7.5) -- (7.5,-0.5) -- (-0.5,-0.5);

\node at (0,-1) {1};
\node at (1,-1) {2};
\node at (2,-1) {3};
\node at (3,-1) {4};
\node at (4,-1) {5};
\node at (5,-1) {6};
\node at (6,-1) {7};
\node at (7,-1) {8};

\node at (8,7) {1};
\node at (8,6) {2};
\node at (8,5) {5};
\node at (8,4) {8};
\node at (8,3) {7};
\node at (8,2) {6};
\node at (8,1) {3};
\node at (8,0) {4};

\end{tikzpicture} &
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\nowire};
\node at (1,0) {\nowire};
\node at (2,0) {\nowire};
\node at (3,0) {\nowire};
\node at (4,0) {\nowire};
\node at (5,0) {\nowire};
\node at (6,0) {\nowire};
\node at (7,0) {\nowire};

\node at (0,1) {\nowire};
\node at (1,1) {\nowire};
\node at (2,1) {\nowire};
\node at (3,1) {\nowire};
\node at (4,1) {\nowire};
\node at (5,1) {\nowire};
\node at (6,1) {\nowire};
\node at (7,1) {\nowire};

\node at (0,2) {\nowire};
\node at (1,2) {\nowire};
\node at (2,2) {\nowire};
\node at (2,2) {2};
\node at (3,2) {\nowire};
\node at (3,2) {2};
\node at (4,2) {\nowire};
\node at (5,2) {\nowire};
\node at (6,2) {\nowire};
\node at (7,2) {\nowire};

\node at (0,3) {\nowire};
\node at (1,3) {\nowire};
\node at (2,3) {\nowire};
\node at (2,3) {2};
\node at (3,3) {\nowire};
\node at (3,3) {2};
\node at (4,3) {\nowire};
\node at (5,3) {\nowire};
\node at (6,3) {\nowire};
\node at (7,3) {\nowire};

\node at (0,4) {\nowire};
\node at (1,4) {\nowire};
\node at (2,4) {\nowire};
\node at (3,4) {\nowire};
\node at (4,4) {\nowire};
\node at (5,4) {\nowire};
\node at (6,4) {\nowire};
\node at (7,4) {\nowire};

\node at (0,5) {\nowire};
\node at (1,5) {\nowire};
\node at (1,5) {1};
\node at (2,5) {\nowire};
\node at (2,5) {1};
\node at (3,5) {\nowire};
\node at (3,5) {1};
\node at (4,5) {\nowire};
\node at (5,5) {\nowire};
\node at (5,5) {2};
\node at (6,5) {\nowire};
\node at (7,5) {\nowire};

\node at (0,6) {\nowire};
\node at (1,6) {\nowire};
\node at (2,6) {\nowire};
\node at (3,6) {\nowire};
\node at (3,6) {1};
\node at (4,6) {\nowire};
\node at (5,6) {\nowire};
\node at (6,6) {\nowire};
\node at (7,6) {\nowire};

\node at (0,7) {\nowire};
\node at (0,7) {0};
\node at (1,7) {\nowire};
\node at (1,7) {0};
\node at (2,7) {\nowire};
\node at (3,7) {\nowire};
\node at (4,7) {\nowire};
\node at (5,7) {\nowire};
\node at (6,7) {\nowire};
\node at (7,7) {\nowire};

\node at (0,-1) {};
\node at (1,-1) {};
\node at (2,-1) {};
\node at (3,-1) {};
\node at (4,-1) {};
\node at (5,-1) {};
\node at (6,-1) {};
\node at (7,-1) {};

\node at (8,7) {};
\node at (8,6) {};
\node at (8,5) {};
\node at (8,4) {};
\node at (8,3) {};
\node at (8,2) {};
\node at (8,1) {};
\node at (8,0) {};

\draw[dashed,->] (4.6,5.4) -- (3,7);
\draw[dashed,->] (2.6,6.4) -- (2,7);
\draw[dashed,->] (2.6,5.4) -- (2,6);
\draw[dashed,->] (1.6,5.4) -- (1,6);
\draw[dashed,->] (0.6,5.4) -- (0,6);
\draw[dashed,->] (1.6,3.4) -- (0,5);
\draw[dashed,->] (1.6,2.4) -- (0,4);
\draw[dashed,->] (2.6,3.4) -- (1.6,4.4);

\draw (-0.5,-0.5) -- (-0.5,7.5) -- (7.5,7.5) -- (7.5,-0.5) -- (-0.5,-0.5);

\end{tikzpicture} &
\begin{tikzpicture}[scale=0.4]
\node at (0,4) {\nowire};
\node at (0,4) {6};
\node at (1,4) {\nowire};
\node at (1,4) {6};

\node at (0,5) {\nowire};
\node at (0,5) {5};
\node at (1,5) {\nowire};
\node at (1,5) {5};

\node at (0,6) {\nowire};
\node at (0,6) {3};
\node at (1,6) {\nowire};
\node at (1,6) {3};
\node at (2,6) {\nowire};
\node at (2,6) {3};

\node at (0,7) {\nowire};
\node at (0,7) {1};
\node at (1,7) {\nowire};
\node at (1,7) {1};
\node at (2,7) {\nowire};
\node at (2,7) {2};
\node at (3,7) {\nowire};
\node at (3,7) {3};

\node at (0,-1) {};
\node at (1,-1) {};
\node at (2,-1) {};
\node at (3,-1) {};
\node at (4,-1) {};
\node at (5,-1) {};
\node at (6,-1) {};
\node at (7,-1) {};

\node at (8,7) {};
\node at (8,6) {};
\node at (8,5) {};
\node at (8,4) {};
\node at (8,3) {};
\node at (8,2) {};
\node at (8,1) {};
\node at (8,0) {};
\node at (4,5) {$=\gamma(B)$};
\end{tikzpicture}
\end{tabular}
\]

§ MAPS

§.§ Edelman-Greene insertion
In [4], Edelman and Greene introduced  a variant of the Robinson-Schensted-Knuth (RSK) algorithm that associates tableaux to reduced words.
We work with a slightly modified version mapping each reduced compatible sequence to a pair of tableaux $(\widetilde{P},\widetilde{Q})$.
Our version generalizes column RSK.
The only modification is that when $x$ is inserted into a column already containing $x$, that column is unchanged and $x{+}1$ is inserted into the next column.
See Section <ref> for a complete description.
We use column insertion to ensure the resulting $\widetilde{Q}$-tableau is semi-standard.

Edelman-Greene and RSK are the same when applied to reduced words for Grassmannian permutations since Definition <ref> 2(a) is never required.
Therefore, properties of RSK extend to Edelman-Greene insertion for such reduced compatible sequences.

If $\binom{r_1, r_2, \ldots, r_\ell}{a_1, a_2, \ldots, a_\ell}$ is a reduced compatible sequence for a Grassmannian permutation then

\[
\widetilde{Q} \left( \binom{r_2, \ldots, r_\ell}{a_2, \ldots, a_{\ell}} \right) = \text{jdt} \left( \widetilde{Q} \left( \binom{r_1, r_2, \ldots, r_\ell}{a_1, a_2, \ldots, a_{\ell}} \right) \right).
\]

§.§ The Gao-Huang Bijection

Recently, Gao and Huang  gave a bijection $\varphi: \text{BPD}(w) \rightarrow \text{PD}(w)$ preserving several important properties [7].
Their map is iterative, with each step performed by an operator $\nabla$ acting on bumpless pipe dreams.
We define $\nabla$ as Definition <ref>.
For $w \in S_\infty$ and $B \in \text{BPD}(w)$, we have $\nabla(B) \in \text{BPD}(v)$ for some $v$ satisfying $\ell(v) = \ell(w) - 1$.
Using $\nabla$, one can construct a pair $\text{pop}(B) = \binom{r}{a}$.

Given $B$ in $\text{BPD}(w)$ with $\ell(w) = \ell$ then

\[
\varphi(B) = \binom{r_1, \ldots, r_\ell}{a_1, \ldots, a_\ell}
\]

where $\binom{r_i}{a_i} = \text{pop}(\nabla^{i-1} B)$ for $1 \leq i \leq \ell$.

See Figure <ref> in Appendix <ref> for an example of this map.
By definition, we have the following relationship between $\varphi(B)$ and $\varphi(\nabla B)$.

If $\varphi(B) = \binom{r_1, r_2, \ldots, r_\ell}{a_1, a_2, \ldots, a_\ell}$ then $\varphi(\nabla B) = \binom{r_2, \ldots, r_\ell}{a_2, \ldots, a_\ell}$.

In [10], an operator equivalent to $\nabla$ was defined for Grassmannian bumpless pipe dreams, where the following property was observed:

Let $w$ be a Grassmannian permutation and $B \in \text{BPD}(w)$.

\[
\text{jdt}(\gamma(B)) = \gamma(\nabla B).
\]

See Figure <ref> after Appendix <ref> for an example of this proposition.

§.§ Little bumps

Monk's rule is a recurrence for Schubert polynomials.
Little bumps are bijections on certain sets of  reduced words [18] that extend[This extension was first described in [12], where Knutson attributes it to Buch.] to bijections on reduced compatible sequences [2], giving a bijective proof of Monk's formula.

For $w \in S_\infty$ and $(i,j)$ such that $\ell(w t_{ij}) = \ell(w) - 1$, the Little bump $L_{ij}$ sends $\binom{\textbf{r}}{\textbf{a}} \in \text{PD}(w)$ to a reduced compatible sequence $L_{ij}\binom{\textbf{r}}{\textbf{a}} = \binom{\textbf{r}}{\textbf{b}}$  for some other permutation $v$.
A precise definition of $L_{ij}$ appears as Definition <ref>.
We require two key properties of the Little bijection.
They are the adaptation of <cit.> and <cit.>, respectively, to our conventions.
Proofs appear in Section <ref>.

Let $w \in S_\infty$.
For every $\binom{\textbf{r}}{\textbf{a}} \in \text{PD}(w)$, there exists a Grassmannian permutation $v$ and  a sequence $L_{i_1j_1}, \dots, L_{i_kj_k}$ of Little bumps so that

\[
L_{i_kj_k} \circ \dots \circ L_{i_1j_1} \binom{\textbf{r}}{\textbf{a}}\in \text{PD}(v).
\]

Let $w \in S_\infty$ and $(i,j)$ so that $\ell(wt_{ij}) = \ell(w) - 1$.
For any $\binom{\textbf{r}}{\textbf{a}} \in \text{PD}(w)$, we have

\[
\widetilde{Q}\left(\binom{\textbf{r}}{\textbf{a}}\right) = \widetilde{Q}\left(L_{ij}\binom{\textbf{r}}{\textbf{a}}\right)
\]

§.§ Huang bumps

In [9] two maps were defined on bumpless pipe dreams to give a combinatorial realization of Monk's formula.
We need one of these maps, which we refer to as a Huang bump in analogy with Little bumps.
A precise definition of Huang bumps appears as Definition <ref>.
Huang bumps and Little bumps are directly related by the Gao-Huang bijection.

Let $w \in S_\infty$ with $\ell(w t_{ij}) = \ell(w) - 1$.
For $B \in \text{BPD}(w)$, we have

\[
(L_{ij} \circ \varphi)(B) = (\varphi \circ H_{ij})(B).
\]

Below is an example for $B \in \text{BPD}(1432)$:

\[
\begin{tikzcd}
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\are};
\node at (2,0) {\cross};
\node at (3,0) {\cross};

\node at (0,1) {\vwire};
\node at (1,1) {\nowire};
\node at (2,1) {\are};
\node at (3,1) {\cross};

\node at (0,2) {\are};
\node at (1,2) {\jay};
\node at (2,2) {\nowire};
\node at (3,2) {\are};

\node at (0,3) {\nowire};
\node at (1,3) {\are};
\node at (2,3) {\hwire};
\node at (3,3) {\hwire};

\draw[thick] (-0.5,0) -- (-0.5,4) -- (3.5,4) -- (3.5,0) -- (-0.5,0);

\node at (4,3) {1};
\node at (4,2) {4};
\node at (4,1) {3};
\node at (4,0) {2};
\node at (-2,2) {$B = $};
\end{tikzpicture} \arrow[start anchor=26.8, end anchor= real west]{r}{\text{embed}} &
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\vwire};
\node at (2,0) {\vwire};
\node at (3,0) {\vwire};
\node at (4,0) {\are};

\node at (0,1) {\vwire};
\node at (1,1) {\are};
\node at (2,1) {\cross};
\node at (3,1) {\cross};
\node at (4,1) {\hwire};

\node at (0,2) {\vwire};
\node at (1,2) {\nowire};
\node at (2,2) {\are};
\node at (3,2) {\cross};
\node at (4,2) {\hwire};

\node at (0,3) {\are};
\node at (1,3) {\jay};
\node at (2,3) {\nowire};
\node at (3,3) {\are};
\node at (4,3) {\hwire};

\node at (0,4) {\nowire};
\node at (1,4) {\are};
\node at (2,4) {\hwire};
\node at (3,4) {\hwire};
\node at (4,4) {\hwire};

\draw[thick] (-0.5,0) -- (-0.5,5) -- (4.5,5) -- (4.5,0) -- (-0.5,0);

\node at (5,4) {1};
\node at (5,3) {4};
\node at (5,2) {3};
\node at (5,1) {2};
\node at (5,0) {5};
\end{tikzpicture} \arrow[start anchor = real east, end anchor = real west]{r}{H_{3 \: 4}} \arrow{d}{\varphi} &
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {\vwire};
\node at (1,0) {\vwire};
\node at (2,0) {\vwire};
\node at (3,0) {\are};
\node at (4,0) {\cross};

\node at (0,1) {\vwire};
\node at (1,1) {\are};
\node at (2,1) {\cross};
\node at (3,1) {\hwire};
\node at (4,1) {\cross};

\node at (0,2) {\vwire};
\node at (1,2) {\nowire};
\node at (2,2) {\are};
\node at (3,2) {\jay};
\node at (4,2) {\are};

\node at (0,3) {\are};
\node at (1,3) {\jay};
\node at (2,3) {\nowire};
\node at (3,3) {\are};
\node at (4,3) {\hwire};

\node at (0,4) {\nowire};
\node at (1,4) {\are};
\node at (2,4) {\hwire};
\node at (3,4) {\hwire};
\node at (4,4) {\hwire};

\draw[thick] (-0.5,0) -- (-0.5,5) -- (4.5,5) -- (4.5,0) -- (-0.5,0);

\node at (5,4) {1};
\node at (5,3) {3};
\node at (5,2) {5};
\node at (5,1) {2};
\node at (5,0) {4};
\end{tikzpicture} \arrow{d}{\varphi} \\
\binom{1,2,3}{3,2,3} \arrow{r}{L_{3 \: 4}} &
\binom{1,2,3}{4,2,3}
\end{tikzcd}
\]

We require one technical property of Huang bumps.
This follows from Lemma <ref>, which states that Huang bumps for vexillary permutations do not alter the location of $\inlinenowire$-tiles.

If $B$ and $B' = H_{ij}(B)$ are bumpless pipe dreams for vexillary permutations, then $\gamma(B) = \gamma(B')$.

§ MAIN RESULTS

We now state Lenart's bijection.

For $v$ a vexillary permutation, the map $\widetilde{Q}: \text{PD}(v) \rightarrow \text{SSYT}_{\phi(v)}(\lambda(v))$ is a bijection.

In this section, we will prove Theorem <ref> by showing the Gao-Huang bijection $\varphi: \text{BPD}(v) \rightarrow \text{PD}(v)$ preserves the underlying semistandard Young tableau associated to $B$ in $\text{BPD}(v)$ and $\varphi(B)$ in $\text{PD}(v)$.

[ampersand replacement=&]
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;
at (5,0) ;
at (6,0) ;
at (7,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;
at (5,1) ;
at (6,1) ;
at (7,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;
at (5,2) ;
at (6,2) ;
at (7,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;
at (5,3) ;
at (6,3) ;
at (7,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;
at (5,4) ;
at (6,4) ;
at (7,4) ;

at (0,5) ;
at (1,5) ;
at (2,5) ;
at (3,5) ;
at (4,5) ;
at (5,5) ;
at (6,5) ;
at (7,5) ;

at (0,6) ;
at (1,6) ;
at (2,6) ;
at (3,6) ;
at (4,6) ;
at (5,6) ;
at (6,6) ;
at (7,6) ;

at (0,7) ;
at (1,7) ;
at (2,7) ;
at (3,7) ;
at (4,7) ;
at (5,7) ;
at (6,7) ;
at (7,7) ;

(-0.5,0) – (-0.5,8) – (7.5,8) – (7.5,0) – (-0.5,0);

at (0,-1) 1;
at (1,-1) 2;
at (2,-1) 3;
at (3,-1) 4;
at (4,-1) 5;
at (5,-1) 6;
at (6,-1) 7;
at (7,-1) 8;

at (8,7) 1;
at (8,6) 2;
at (8,5) 5;
at (8,4) 8;
at (8,3) 7;
at (8,2) 6;
at (8,1) 3;
at (8,0) 4;
[start anchor=real east, end anchor=real west]rrφ drγ & &
at (0,-1) ;

at (0,0) ;
at (1,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;
at (5,4) ;

at (0,5) ;
at (1,5) ;
at (2,5) ;
at (3,5) ;
at (4,5) ;
at (5,5) ;
at (6,5) ;

at (0,6) ;
at (1,6) ;
at (2,6) ;
at (3,6) ;
at (4,6) ;
at (5,6) ;
at (6,6) ;
at (7,6) ;

at (0,7.5) 1;
at (1,7.5) 2;
at (2,7.5) 3;
at (3,7.5) 4;
at (4,7.5) 5;
at (5,7.5) 6;
at (6,7.5) 7;
at (7,7.5) 8;

at (-1,6) 1;
at (-1,5) 2;
at (-1,4) 5;
at (-1,3) 8;
at (-1,2) 7;
at (-1,1) 6;
at (-1,0) 3;
at (-1,-1) 4;

(-0.5,-1) – (-0.5,7) – (7.5,7);

at (5.5,-0.25) $\binom{1,1,2,3,3,3,3,5,5,6,6}{5,4,3,7,6,5,4,6,5,7,6}$;

1     1     2     3

3     3     3

5     5

6     6

An example of the maps.

We first prove the statement for Grassmannian permutations.
Our argument uses the following observation.

For $w$ Grassmannian and $B \in \text{BPD}(w)$ one has

\[
\text{jdt}(\widetilde{Q}(\varphi(B))) = \widetilde{Q}(\varphi(\nabla B)).
\]

The result follows by combining Proposition <ref> and Lemma <ref> with Proposition <ref>.

For $w$ Grassmannian with descent in position $k$, the following diagram commutes:

\[
\begin{tikzcd}
\text{BPD}(w) \arrow{rr}{\varphi} \arrow{dr}{\gamma} & & \text{PD}(w) \arrow[swap]{dl}{\widetilde{Q}} \\ & \text{SSYT}_k(w) &
\end{tikzcd}
\]

Let $\ell(w) = p$ and $B \in \text{BPD}(w)$.
We will show $\gamma(B) = \widetilde{Q}(\varphi(B))$ using induction on $p$.
If $p = 0$ then all objects are empty and the result holds.
Now suppose $p \geq 1$ and that the statement holds for all Grassmannian $w'$ with $\ell(w') < p$.
Write $\text{pop}(B) = \binom{r}{a}$.
By definition $\nabla B \in \text{BPD}(s_a w)$.
Moreover, $w' = s_a w$  is Grassmannian with $\ell(w') = p - 1$.
We now compute

\begin{align*}
\widetilde{Q}(\varphi(B)) &= \text{jdt}^{-1}(\widetilde{Q}(\varphi(\nabla B)))  \tag{Lemma~\ref{l:grassmannian-induction}} \\
&= \text{jdt}^{-1}(\gamma({\nabla B})) \tag{Induction} \\
&= \gamma(B) \tag{Proposition~\ref{p:HuangCor}}.
\end{align*}

This completes our proof.

Next, we obtain our main result, extending Theorem <ref> to all vexillary permutations using Little bumps and Huang bumps.

For $v$ vexillary, the following diagram commutes:

\[
\begin{tikzcd}
\text{BPD}(v) \arrow{rr}{\varphi} \arrow{dr}{\gamma} & & \text{PD}(v) \arrow[swap]{dl}{\widetilde{Q}} \\ & \text{SSYT}_{\phi(v)}(\lambda(v)) &
\end{tikzcd}
\]

Let $B \in \text{BPD}(v)$ and $P  = \varphi(B)$.
By Proposition <ref>, there exists a sequence of Little bumps $L_{i_1j_1}, \dots, L_{i_kj_k}$ so that

\[
P' = L_{i_kj_k} \circ \dots \circ L_{i_1 j_1} P
\]
is a reduced compatible sequence for a Grassmannian permutation $w$.
Set $B' = \varphi^{-1}(P')$.
By applying Theorem <ref> repeatedly, we then have

\[
B' = H_{i_kj_k} \circ \dots \circ H_{i_1 j_1} B.
\]

Then $\gamma(B) = \gamma(B') = \widetilde{Q}(P') = \widetilde{Q}(P) = \widetilde{Q}(\varphi(B))$, with the first three equalities following from
Corollary <ref>, Theorem <ref> and Proposition <ref>, respectively and the fourth by construction.

Since $\varphi$ and $\gamma$ are bijections, Theorem <ref> is an immediate corollary.

§ HUANG BUMPS AND THE LITTLE BIJECTION

The Little bijection, as originally defined, maps a reduced word $\textbf{a}$ to a tableau $\text{LS}(\mathbf{a})$ and path $(w^1,\dots,w^k)$ of permutations in the Lascoux-Schützenberger tree.
To invert the map, one sends $\text{LS}(\textbf{a})$ to a Grassmannian reduced word with appropriate descent, then applies a Little bump for each edge in the path.
The main result of [8] shows that (with appropriate conventions) $\text{LS}(\textbf{a}) = \widetilde{Q}(\textbf{a})$.
In principle, the data encoded by $(w^1,\dots,w^k)$ and $\widetilde{P}(\textbf{a})$ are equivalent, but a direct correspondence is not known.
One subtlety is that the Little bijection frequently requires working with permutations whose support contains negative values.

In Sections <ref> and <ref>, we present an extension of Little bumps to pipe dreams.
The Little bijection extends to biwords via the same filling procedure we give to construct $\widetilde{Q}$ in Section <ref>.
However, the intermediate biwords constructed via the original map may violate the reduced compatible conditions.
By instead applying the sequence of bumps constructed in Proposition <ref>, one has a construction for pipe dreams in the spirit of the original Little bijection, which we call the Little bijection for pipe dreams.

The canonical nature of the Gao-Huang bijection (Theorem <ref>) allows one to work with Little bumps for pipe dreams and Huang bumps for bumpless pipe dreams interchangeably.
In particular, the pipe dream analogue of the Little bijection for pipe dreams extends to Huang bumps.

Let $w \in S_\infty$, $B \in \text{BPD}(w)$ and $P = \varphi(B)$.
With $L_{i_1j_1} \dots L_{i_kj_k}$ the sequence of Little bumps for $P$ in Proposition <ref>, the Huang bijection maps $B$ to the pair

\[
(w^0, w^1, \dots, w^k) \quad \mbox{and} \quad \text{LS}(B) = \gamma \left( H_{i_kj_k} \circ \dots \circ H_{i_1 j_1} B\right)
\]

where $w^0 = w$ and  $w^\ell$ is the permutation of $H_{i_\ell j_\ell} \circ \dots \circ H_{i_1 j_1} B$ for $\ell > 0$.

By repeated application of $\varphi$ and Theorem <ref>, we see the Huang bijection is well-defined.
Moreover, it is invertible since $\gamma$ is invertible and each Huang bump is invertible if one knows the source permutation.

The Huang bijection and the Little bijection for pipe dreams coincide.

This follows from the previous discussion and the fact that $\gamma$ coincides with usual correspondence for Grassmannian reduced words, which follows from Theorem <ref> and <cit.>.

The bulk of our proof for Theorem <ref> is embedded in Proposition <ref>.
The only missing piece is Corollary <ref>, which equivalently shows we only need to apply Huang bumps in Definition <ref> until the corresponding permutation $w^\ell$ is vexillary.

For the vexillary case, we understand the range of these maps precisely: the path of permutations is deterministic and $\text{LS}$ maps to flagged tableaux.
Outside of this setting the set of paths can be determined, but the image of $\text{LS}$ does not have a simple description.
However, Proposition <ref> applies, giving:

For $w \in S_\infty$ and $B \in \text{BPD}(w)$, we have

\[
\text{LS}(B) = \widetilde{Q}(\varphi(B)).
\]

In principle, the sequence of permutations
constructed in the Huang bijection encodes the same data as the Edelman-Greene insertion tableau $\widetilde{P}(\varphi(B))$.
However, there is no immediate correspondence.
There is another way to associate an insertion tableau to a bumpless pipe dream, obtained by composing the map in <cit.> with either the map $\Omega$ in <cit.> or the map in <cit.>, but it is unclear whether either is consistent with $\text{LS}$.
Forthcoming work of Huang, Shimozono and Yu gives another, more general, realization of Edelman-Greene insertion on bumpless pipe dreams [23], so we choose not to pursue this direction further.

Recently, Huang and Pylyavskyy introduced two new bijections mapping bumpless pipe dreams to labeled chains of permutations [11].
Neither of their maps are precisely equivalent to the Huang bijection we describe, but they encode the same data.
Both maps are based on what we call inverse Huang bumps, and their right insertion is equivalent to the map in [2].
One difference is that their chains involve permutations with different lengths, while the permutations in the Huang bijection all have the same length.

§ DETAILS OF MAPS

§.§ Edelman-Greene insertion

Let $C = \{c_1 < \ldots < c_\ell\}$.
The Edelman-Greene insertion rule for inserting a positive integer $x \neq c_\ell$ into $C$ is as follows:

1.) If $C$ is empty or $x > c_{\ell}$  then append $x$ to the bottom of $C$.

2.) If $x < c_{\ell}$ let $k$ be the smallest row index for which $x < c_k$.

(a) If $c_k = x+1$ and $c_{k-1} = x$ then leave $C$ unchanged.

(b) Otherwise, replace $c_k$ with $x$.

Using the Edelman-Greene insertion rule, we explain how to insert an entry into a tableau.

Let $T$ be a semistandard tableau with columns $C_1, \ldots, C_m$ where $C_i = \{c_1^i < \ldots < c_{\ell_i}^i\}$.
To Edelman-Greene insert $x$ into $T$, denoted $T \uparrow x$, iterate the following:
Using the Edelman-Greene insertion rule, insert $x$ into $C_1$.

1.) If $x$ was appended to the bottom of $C_1$ then stop.

2.) If $C_1$ was left unchanged then insert $x+1$ into the tableau with columns $C_2, \ldots, C_m$.

3.) If $x$ replaced $c_k^1$ in $C_1$ then insert $c_k^1$ into the tableau with columns $C_2, \ldots, C_m$.

Note this algorithm is not well defined for all integers and tableaux, since we could have $x = c_\ell$.
Item 2 is where Edelman-Greene insertion differs from RSK.

For a reduced compatible sequence $\binom{\mathbf{r}}{\mathbf{a}} = \binom{r_1, \ldots, r_\ell}{a_1, \ldots, a_\ell}$, use the Edelman-Greene algorithm to output a pair of tableaux $(\widetilde{P},\widetilde{Q})$ as follows. The $\widetilde{P}$-tableau is

\[
\widetilde{P}\left( \binom{\mathbf{r}}{\mathbf{a}} \right) = (((\varnothing \uparrow a_1) \uparrow a_2) \ldots \uparrow a_\ell).
\]

Meanwhile, the $\widetilde{Q}$-tableau is constructed simultaneously by placing $r_i$ in the new box created when inserting $a_i$.

It is a non-trivial fact that, when inserting a reduced word, every step is well-defined during this process [4].

For example, one has

\begin{align*}
\widetilde{P}\left( \binom{1,1,2,2}{4,2,3,2} \right) &: \quad
\varnothing \quad
\begin{ytableau}
\end{ytableau} \quad
\begin{ytableau}
2 & 4
\end{ytableau} \quad
\begin{ytableau}
2 & 4 \\ 3
\end{ytableau} \quad
\begin{ytableau}
2 & 3 & 4 \\ 3
\end{ytableau} \\
\widetilde{Q}\left( \binom{1,1,2,2}{4,2,3,2} \right) &: \quad
\varnothing \quad
\begin{ytableau}
\end{ytableau} \quad
\begin{ytableau}
1 & 1
\end{ytableau} \quad
\begin{ytableau}
1 & 1 \\ 2
\end{ytableau} \quad
\begin{ytableau}
1 & 1 & 2 \\ 2
\end{ytableau}
\end{align*}

where Definition <ref> 2(a) was used when inserting the second $2$.

§.§ The Gao-Huang bijection

Given a bumpless pipe dream $B$ write $B_{ij}$ for the tile of $B$ in location $(i,j)$. Let $B(\inlinenowire)$ denote the set of $(i,j)$ such that $B_{ij} = \inlinenowire$ and likewise for other tiles.
We now recall droop moves on a bumpless pipe dream.

For a bumpless pipe dream $B$, say there is an available droop from $(i,j)$ into $(k,\ell)$ with $k > i$ and $\ell > j$ if

\[
B_{ij} = \are, \quad B_{k \ell} = \nowire, \quad \text{and} \quad B_{pq} \neq \are, \jay
\]

for any $i \leq p \leq k$ and $j \leq q \leq \ell$. When available, a droop move from $(i,j)$ into $(k,\ell)$ reroutes the pipe going through $(i,j)$ to instead go through $(k,\ell)$ as shown below.

\[
\begin{tikzcd}
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {$k$};
\node at (0,3) {$i$};
\node at (4,6) {$j$};
\node at (8,6) {$\ell$};
\node at (4,0) {\vwire};
\node at (4,1) {\vwire};
\node at (4,2) {\vwire};
\node at (4,3) {\are};
\node at (5,3) {\hwire};
\node at (6,3) {\hwire};
\node at (7,3) {\hwire};
\node at (8,3) {\hwire};
\node at (8,0) {\nowire};
\node at (7,0) {\shade};
\node at (6,0) {\shade};
\node at (5,0) {\shade};
\node at (5,1) {\shade};
\node at (6,1) {\shade};
\node at (7,1) {\shade};
\node at (8,1) {\shade};
\node at (8,2) {\shade};
\node at (7,2) {\shade};
\node at (6,2) {\shade};
\node at (5,2) {\shade};

\draw[dashed] (1,-2) -- (1,5) -- (10,5);
\end{tikzpicture} \arrow[start anchor = real east, end anchor = real west]{r}{\text{droop}} &
\begin{tikzpicture}[scale=0.4]
\node at (0,0) {$k$};
\node at (0,3) {$i$};
\node at (4,6) {$j$};
\node at (8,6) {$\ell$};
\node at (4,0) {\are};
\node at (4,1) {\shade};
\node at (4,2) {\shade};
\node at (4,3) {\nowire};
\node at (5,3) {\shade};
\node at (6,3) {\shade};
\node at (7,3) {\shade};
\node at (8,3) {\are};
\node at (8,0) {\jay};
\node at (7,0) {\hwire};
\node at (6,0) {\hwire};
\node at (5,0) {\hwire};
\node at (5,1) {\shade};
\node at (6,1) {\shade};
\node at (7,1) {\shade};
\node at (8,1) {\vwire};
\node at (8,2) {\vwire};
\node at (7,2) {\shade};
\node at (6,2) {\shade};
\node at (5,2) {\shade};

\draw[dashed] (1,-2) -- (1,5) -- (10,5);
\end{tikzpicture}
\arrow[start anchor = base west, end anchor = base east]{l}{\text{undroop}}
\end{tikzcd}
\]

The $\inlineshade$-tiles must be from $\{\inlinenowire, \inlinevwire, \inlinehwire, \inlinecross\}$ and the $\inlinevwire$ and $\inlinehwire$ tiles might actually be $\inlinecross$ tiles in $B$.
Note that droop moves are invertible.
An undroop from $(k,\ell)$ into $(i,j)$ is the inverse of the droop move from $(i,j)$ into $(k,\ell)$.

We now give the definition of $\nabla$.

Given $B$ in $\text{BPD}(w)$, the following procedure records $\text{pop}(B) = \binom{r}{a}$ and creates $\nabla B$ in $\text{BPD}(s_a w)$.
To begin, let $r$ be the smallest row index in which $B$ has $\inlinenowire$-tiles. Mark the rightmost $\inlinenowire$-tile in row $r$ with an $\times$.

(1) Move the mark $\times$ to the rightmost $\inlinenowire$-tile in a contiguous block of $\inlinenowire$-tiles in its row. Let $(i,j)$ be the location of the marked tile and let $p$ be the pipe going through $(i,j+1)$.

(2) If $p \neq j+1$ then it must have a $\inlinejay$-tile at $(i',j+1)$ for some $i' > i$. Consider the $(i'-i) \times 2$ rectangle $R$ with northwest corner $(i,j)$ and southeast corner $(i',j+1)$.

(a) For any pipe $q$ crossing through $R$ having both a $\inlineare$-tile and a $\inlinejay$-tile in column $j$, say in rows $i < k < k' < i'$, droop the pipe $q$ at $(k,j)$ into $(k',j+1)$ whilst ignoring the pipe $p$.

(b) Undroop pipe $p$ at $(i',j+1)$ into $(i,j)$. Move the mark $\times$ to $(i',j+1)$ and go back to Step (1).

(3) If $p = j+1$ then pipes $j$ and $j+1$ must intersect at some $(i',j+1)$ with $i' > i$. Replace this $\inlinecross$-tile with a $\inlinebump$-tile but then immediately undroop the $\inlinejay$-turn of pipe $j$ in this $\inlinebump$-tile into $(i,j)$, adjusting any intersecting pipes between rows $i$ and $i'$ in the same fashion as Step 2(a) above. Set $a = j$, the column index of the left column in this last $(i'-i) \times 2$ rectangle of tiles to be modified. The result is a bumpless pipe dream $\nabla B$ for $s_a w$.

The process ends after Step (3) and we output $\text{pop}(B) = \binom{r}{a}$ and $\nabla B$.
See Figure <ref> for examples of $\nabla$ and $\text{Pop}$.

[ampersand replacement=&]
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;

(-0.5,0) – (-0.5,5) – (4.5,5) – (4.5,0) – (-0.5,0);
dφ [start anchor=real east, end anchor=real west]r13 &
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;

(-0.5,0) – (-0.5,5) – (4.5,5) – (4.5,0) – (-0.5,0);
[start anchor=real east, end anchor=real west]r11 &
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;

(-0.5,0) – (-0.5,5) – (4.5,5) – (4.5,0) – (-0.5,0);

at (0,0) ;

at (0,1) ;
at (1,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;

at (3,0) $\binom{1,1,2,3}{3,1,4,3}$;

(-0.5,0) – (-0.5,5) – (4.5,5);
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;

(-0.5,0) – (-0.5,5) – (4.5,5) – (4.5,0) – (-0.5,0);
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;

(-0.5,0) – (-0.5,5) – (4.5,5) – (4.5,0) – (-0.5,0);
[start anchor=real west, end anchor=real east, swap]l33

The Gao-Huang bijection.

[ampersand replacement=&]
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;
at (5,0) ;
at (6,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;
at (5,1) ;
at (6,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;
at (5,2) ;
at (6,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;
at (5,3) ;
at (6,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;
at (5,4) ;
at (6,4) ;

at (0,5) ;
at (1,5) ;
at (2,5) ;
at (3,5) ;
at (4,5) ;
at (5,5) ;
at (6,5) ;

at (0,6) ;
at (1,6) ;
at (2,6) ;
at (3,6) ;
at (4,6) ;
at (5,6) ;
at (6,6) ;

[thick] (-0.5,0) – (-0.5,7) – (6.5,7) – (6.5,0) – (-0.5,0);
[start anchor=real east, end anchor=real west]r15 dγ &
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;
at (5,0) ;
at (6,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;
at (5,1) ;
at (6,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;
at (5,2) ;
at (6,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;
at (5,3) ;
at (6,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;
at (5,4) ;
at (6,4) ;

at (0,5) ;
at (1,5) ;
at (2,5) ;
at (3,5) ;
at (4,5) ;
at (5,5) ;
at (6,5) ;

at (0,6) ;
at (1,6) ;
at (2,6) ;
at (3,6) ;
at (4,6) ;
at (5,6) ;
at (6,6) ;

[thick] (-0.5,0) – (-0.5,7) – (6.5,7) – (6.5,0) – (-0.5,0);
[start anchor=real east, end anchor=real west]r11 dγ &
at (0,0) ;
at (1,0) ;
at (2,0) ;
at (3,0) ;
at (4,0) ;
at (5,0) ;
at (6,0) ;

at (0,1) ;
at (1,1) ;
at (2,1) ;
at (3,1) ;
at (4,1) ;
at (5,1) ;
at (6,1) ;

at (0,2) ;
at (1,2) ;
at (2,2) ;
at (3,2) ;
at (4,2) ;
at (5,2) ;
at (6,2) ;

at (0,3) ;
at (1,3) ;
at (2,3) ;
at (3,3) ;
at (4,3) ;
at (5,3) ;
at (6,3) ;

at (0,4) ;
at (1,4) ;
at (2,4) ;
at (3,4) ;
at (4,4) ;
at (5,4) ;
at (6,4) ;

at (0,5) ;
at (1,5) ;
at (2,5) ;
at (3,5) ;
at (4,5) ;
at (5,5) ;
at (6,5) ;

at (0,6) ;
at (1,6) ;
at (2,6) ;
at (3,6) ;
at (4,6) ;
at (5,6) ;
at (6,6) ;

[thick] (-0.5,0) – (-0.5,7) – (6.5,7) – (6.5,0) – (-0.5,0);

1   1   2
2     3     3
3     4
rjdt(γ(B)) &

1     2     3
2     3
3     4
rjdt(γ(∇B)) &

2     2     3
3     3
4     4

An illustration of Proposition <ref>.

§.§ Little bumps

We define Little bumps.

Let $w \in S_\infty$ and fix $(i,j)$ so that $\ell(w t_{ij}) = \ell(w) - 1$.
The (upward) Little bump $L_{ij}$ takes as input some $\binom{\textbf{r}}{\textbf{a}} \in \text{PD}(w)$.
Fix $m$ so that wires $i$ and $j$ cross in the $\inlinecross$-tile corresponding to $\binom{r_{m}}{a_{m}}$.

* Set $\textbf{a}^{(1)} := \textbf{a}$, $m_1 := m$ and $k = 1$.

* Replace $\binom{r_{m_k}}{a_{m_k}}$ with $\binom{r_{m_k}}{a_{m_1}+k}$ to obtain a new biword $\binom{\textbf{r}}{\textbf{a}^{(k)}}$.

* If $\textbf{a}^{(k)}$ is a reduced word, return $\binom{\textbf{r}}{\textbf{a}^{(k)}}$.
Otherwise, there exists a unique index $m_{k+1} \neq m_{k}$ so that the wires crossing in the $\inlinecross$-tile corresponding to $\binom{r_{m_k}}{a_{m_k}+1}$ are the same as those crossing in the $\inlinecross$-tile corresponding to $\binom{r_{m_{k+1}}}{a_{m_{k+1}}}$ (note these $\inlinecross$-tiles could coincide).
Repeat (2) using $k+1$.

Call the output $L_{ij}\binom{\textbf{r}}{\textbf{a}}$.

It is far from obvious that this map is well-defined, that it eventually terminates or that it is invertible.
The fact that the compatible sequence property is preserved follows from the fact that $L_{ij}$ preserves descent sets of reduced words <cit.> and increments values.
We now give proofs of Propositions <ref> and <ref>.

This is a straightforward consequence of <cit.>, which says such a sequence of inverse or downward Little bumps exists for every reduced word.
To see why, let $w \in S_m$.
Map $\textbf{a} \mapsto \textbf{b}$ via $a_i \mapsto b_i = m-a_i$.
This map preserves the property that $\textbf{a}$ is a reduced word of a Grassmannian permutation.
Via this map, a downward Little bump on $\textbf{b}$ corresponds to an upward Little bump on $\textbf{a}$.
Therefore, the sequence of downward Little bumps mapping $\textbf{b}$ to Grassmannian reduced word $\textbf{b}'$ corresponds to a sequence of (upward) Little bumps mapping $\binom{\textbf{r}}{\textbf{a}}$ to $\binom{\textbf{r}}{\textbf{a}'}$ where $\textbf{a}'$ is a Grassmannian reduced word.

This is the biword version of <cit.>, as applied to column Edelman-Greene insertion.
The original statement is for row Edelman-Greene insertion, which differs by transposing the insertion and recording tableaux.
To upgrade to biwords, note we are inserting the same sequence $\textbf{r}$ into the same standard tableaux.
The result now follows.

§.§ Huang bumps

An almost bumpless pipe dream is a bumpless pipe dream or a diagram with at most one $\inlinebump$, but otherwise satisfies the definition of a bumpless pipe dream.
In order to define Huang bumps, we require two additional maps known as Monk moves.

Fix an almost bumpless pipe dream.

(i) min-droop: Let $(i,j)$ be a $\inlineare$-turn of a pipe $p$, which could be either a $\inlineare$-tile or a $\inlinebump$-tile. Let $k,\ell \geq 1$ be the smallest numbers such that $(i+k,j)$ and $(i,j+\ell)$ are not $\inlinecross$-tiles. A min-droop at $(i,j)$ droops pipe $p$ into $(i+k,j+\ell)$.

(ii) cross-bump-swap: Let $(i,j)$ be a $\inlinebump$-tile of pipes $p$ and $q$ and suppose $p$ and $q$ cross each other at $(k,\ell)$. A cross-bump-swap move at $(i,j)$ swaps the $\inlinebump$-tile at $(i,j)$ with the $\inlinecross$-tile at $(k,\ell)$.

We are now prepared to define a Huang bump.

Let $w$ be a permutation such that $w(i) > w(j)$ for some $i < j$. Given $B$ in $\text{BPD}(w)$, the following gives $H_{ij}(B)$.

(1) Initialize $(x,y)$ as the $\inlinecross$-tile where pipes $i$ and $j$ cross. Replace this tile with a $\inlinebump$-tile.

(2) Perform a min-droop at $(x,y)$ and let $(x',y')$ record the southeast corner of this droop.

(a) If $(x',y')$ is a $\inlinejay$-tile then update $(x,y)$ to be the position of the $\inlineare$-tile of pipe $i$ in row $x'$ and repeat Step 2.

(b) If $(x',y')$ is a $\inlinebump$-tile, let $k$ be the pipe of the $\inlineare$-turn of $(x',y')$.

(i) If $i$ and $k$ cross each other at $(x'',y'')$ then perform a cross-bump-swap at $(x',y')$. Update $(x,y) = (x'',y'')$ and repeat Step 2.

(ii) If $i$ and $k$ never cross each other then replace $(x',y')$ with a $\inlinecross$-tile and stop.

To prove Lemma <ref>, we require a property of vexillary bumpless pipe dreams.

Suppose $v$ is vexillary and let $\rho(v)$ denote the smallest partition such that $Y_{\rho(v)} \supseteq D_v$. Then one has $B(\inlinecross) \cap Y_{\rho(v)} = \varnothing$ for each $B$ in $\text{BPD}(v)$.

If $B$ and $B' = H_{ij}(B)$ are bumpless pipe dreams for vexillary permutations, then $B$ and $B'$ agree on $Y_{\rho(v)}$.

In $H_{ij}$ we initialize at a $\inlinecross$-tile and perform basic Monk moves that only have an affect on tiles outside of $Y_{\rho(v)}$ by Lemma <ref>.

[1]
Nantel Bergeron and Sara Billey.
RC-graphs and Schubert polynomials.
Experimental Mathematics, 2(4):257–269, 1993.

[2]
Sara C Billey, Alexander E Holroyd, and Benjamin J Young.
A bijective proof of Macdonald's reduced word formula.
Algebraic Combinatorics, 2(2):217–248, 2019.

[3]
Sara C Billey, William Jockusch, and Richard P Stanley.
Some combinatorial properties of Schubert polynomials.
Journal of Algebraic Combinatorics, 2(4):345–374, 1993.

[4]
Paul Edelman and Curtis Greene.
Balanced tableaux.
Advances in Mathematics, 63(1):42–99, 1987.

[5]
Neil JY Fan, Peter L Guo, and Sophie CC Sun.
Bumpless pipedreams, reduced word tableaux and Stanley symmetric
arXiv preprint arXiv:1810.11916, 2018.

[6]
William Fulton.
Young tableaux: with applications to representation theory and
Number 35. Cambridge University Press, 1997.

[7]
Yibo Gao and Daoji Huang.
The canonical bijection between pipe dreams and bumpless pipe dreams.
arXiv preprint arXiv:2108.11438, 2021.

[8]
Zachary Hamaker and Benjamin Young.
Relating Edelman–Greene insertion to the Little map.
Journal of Algebraic Combinatorics, 40(3):693–710, 2014.

[9]
Daoji Huang.
Bijective proofs of Monk's rule for Schubert and double
Schubert polynomials with bumpless pipe dreams.
arXiv preprint arXiv:2010.15048, 2020.

[10]
Daoji Huang.
Schubert products for permutations with separated descents.
arXiv preprint arXiv:2105.01591, 2021.

[11]
Daoji Huang and Pavlo Pylyavskyy.
Bumpless pipe dream RSK, growth diagrams, and Schubert structure
arXiv preprint arXiv:2206.1435, 2022.

[12]
Allen Knutson.
Schubert polynomials and symmetric functions –notes for the Lisbon
Combinatorics Summer School, 2012.

[13]
Allen Knutson, Ezra Miller, and Alexander Yong.
Gröbner geometry of vertex decompositions and of flagged
Journal fur die Reine und Angewandte Mathematik, (630):1–31,

[14]
Victor Kreiman.
Schubert classes in the equivariant K-theory and equivariant
cohomology of the Lagrangian Grassmannian.
arXiv preprint arXiv:math/0602245, 2006.

[15]
Thomas Lam, Seung Jin Lee, and Mark Shimozono.
Back stable Schubert calculus.
Compositio Mathematica, 157(5):883–962, 2021.

[16]
Alain Lascoux.
Chern and Yang through ice.
preprint, page 10pp, 2008.

[17]
Cristian Lenart.
A unified approach to combinatorial formulas for Schubert
Journal of Algebraic Combinatorics, 20(3):263–299, 2004.

[18]
David P Little.
Combinatorial aspects of the Lascoux–Schützenberger tree.
Advances in Mathematics, 174(2):236–253, 2003.

[19]
Bruce Sagan.
The symmetric group: representations, combinatorial
algorithms, and symmetric functions, volume 203.
Springer Science & Business Media, 2001.

[20]
Luis Serrano and Christian Stump.
Maximal fillings of moon polyominoes, simplicial complexes, and
Schubert polynomials.
Electronic Journal of Combinatorics, 19(1):Paper 16, 18, 2012.

[21]
Michelle L Wachs.
Flagged Schur functions, Schubert polynomials, and symmetrizing
Journal of Combinatorial Theory, Series A, 40(2):276–289,

[22]
Anna Weigandt.
Bumpless pipe dreams and alternating sign matrices.
Journal of Combinatorial Theory, Series A, 182:105470, 2021.

[23]
Tianyi Yu.
Private Communication.


4), we can probabilistically prepare $|+\rangle$ 2D cluster states suitable
for quantum computation. The starting lattice (including the ancilla qubits)
is hence the degree $5$ graph illustrated in figure 4. To see how to to
perform universal quantum computation, consider the following sequence of
operations.

Figure 4: This diagram illustrates how to prepare a single $|+\rangle$ state
on the lattice via a linear chain. The linear chain, attached vertically to
the 2D lattice, is built from ancilla qubits that are initialised with certain
specified angles, which are then measured in the $X$-basis. In the method
described in the text and an appendix, one linear chain is attached to each
qubit on the $n\times m$ lattice.

  1. 1.

Prepare two ancilla qubits $|\phi_{1}\rangle$ and $|\phi_{2}\rangle$, where
$|\phi_{j}\rangle=\cos(\phi_{j}/2)|0\rangle+\sin(\phi_{j}/2)|1\rangle$,
$\phi_{j}\in(0,2\pi)$ and the index $j$ denotes the qubit. Additionally, for
technical reasons we impose the condition that
$\phi_{1}+\phi_{2}=\frac{\pi}{2}$.

  2. 2.

Apply a CZ gate between ancilla qubits 1 and 2 and measure the 1st qubit in
the X-basis. If the outcome $x_{1}=1$ is obtained, which occurs with
probability $p_{x_{1}}(1)=\frac{1}{2}(1-\sin{\phi_{1}}\cos{\phi_{2}})$, the
post-measurement state of qubit 2 is

$\displaystyle|\phi_{2}^{\prime}\rangle=$
$\displaystyle\frac{\left[\cos(\phi_{1}/2)-\sin(\phi_{1}/2)\right]\cos(\phi_{2}/2)}{\sqrt{1-\sin{\phi_{1}}\cos{\phi_{2}}}}|0\rangle$
$\displaystyle+$
$\displaystyle\frac{\left[\cos(\phi_{1}/2)+\sin(\phi_{1}/2)\right]\sin(\phi_{2}/2)}{\sqrt{1-\sin{\phi_{1}}\cos{\phi_{2}}}}|1\rangle.$

Therefore, if we pick $\phi_{1}+\phi_{2}=\frac{\pi}{2}$, the post-measurement
state $|\phi_{2}^{\prime}\rangle$ becomes a $|+\rangle$ state.

  3. 3.

If the outcome $x_{1}=0$ is obtained, which occurs with probability
$p_{x_{1}}(0)=\frac{1}{2}(1+\sin{\phi_{1}}\cos{\phi_{2}})$, the post-
measurement state of qubit 2 is

$\displaystyle|\phi_{2}^{\prime}\rangle=$
$\displaystyle\frac{\left[\cos(\phi_{1}/2)+\sin(\phi_{1}/2)\right]\cos(\phi_{2}/2)}{\sqrt{1+\sin{\phi_{1}}\cos{\phi_{2}}}}|0\rangle$
$\displaystyle+$
$\displaystyle\frac{\left[\cos(\phi_{1}/2)-\sin(\phi_{1}/2)\right]\sin(\phi_{2}/2)}{\sqrt{1+\sin{\phi_{1}}\cos{\phi_{2}}}}|1\rangle.$

That is, $|\phi_{2}\rangle$ has undergone a rotation about the $Y$ axis toward
the $|0\rangle$ state.

If the outcome $x_{1}=1$ is obtained, then we have successfully produced a
$|+\rangle$ state which is placed on the lattice. If the wrong outcome
$x_{1}=0$ is obtained, then we initialise another ancilla qubit
$|\phi_{3}\rangle$, such that $\phi_{2}^{\prime}+\phi_{3}=\frac{\pi}{2}$,
where $\phi_{2}^{\prime}$ is the angle of the post-measurement state of qubit
2. We then proceed to repeat the above procedure. That is, we apply a CZ gate
between qubits 2 and 3, and measure qubit 2 in the $X$ basis. Similarly, if
the outcome $x_{2}=1$ is obtained, with probability
$p_{x_{2}}(1)=\frac{1}{2}(1-\sin{\phi^{\prime}_{2}}\cos{\phi_{3}})$, then the
post-measurement state of qubit 3 is $|+\rangle$. If outcome $x_{2}=0$ is
obtained, which occurs with probability
$p_{x_{2}}(0)=\frac{1}{2}(1+\sin{\phi^{\prime}_{2}}\cos{\phi_{3}})$, then the
post-measurement state of qubit 3 is $|\phi^{\prime}_{3}\rangle.$ By repeating
this method, we can calculate the probability that the lattice site will be
occupied by a $|+\rangle$ state. For example, repeating the method for three
ancilla qubits, the probability is

$p_{site}=p_{x_{1}}(1)+p_{x_{1}}(0)\left[p_{x_{2}}(1)+p_{x_{2}}(0)p_{x_{3}}(1)\right].$
(73)

In the case that a $|+\rangle$ has not been successfully prepared on the
lattice by the ancilla chain, we measure the final qubit in the Z basis. This
projects the qubit into the $|0\rangle$ (or $|1\rangle$) state which
corresponds to creating a hole on the lattice, i.e. we have removed a vertex
and edges from the cluster state. According to the percolation threshold
$p_{c}=0.5927\ldots$, if $p_{site}>p_{c}$ then by Dan  we can construct an
efficient LOCC algorithm that creates a perfect cluster state from a 2D
cluster state with holes. We find that by attaching and measuring three
ancilla qubits, with angles $\phi_{1}=0.18\pi$, $\phi_{2}=0.32\pi$ and
$\phi_{3}=0.31\pi$, we can prepare a $|+\rangle$ state on the lattice with
probability $0.73$ which is above the percolation threshold $p_{c}$. The
maximum angle required $\phi_{2}=0.32\pi$ corresponds to $r_{max}=0.84$.
Therefore, we can prepare a $|+\rangle$ state with probability above the
percolation threshold $p_{c}$, with three ancilla that are drawn from within
${\rm Cyl}(r_{max})$ with $r_{max}=0.84$.

## References

  * (1) J. Preskill, Quantum computing 40 years later. arXiv:2106.10522 [quant-ph]
  * (2) R. Raussendorf and H.J. Briegel, A One-Way Quantum Computer. Phys. Rev. Lett. 86, 5188 (2001)
  * (3) A. Harrow and M. Nielsen, Robustness of quantum gates in the presence of noise. Phys. Rev. A 68, 012308 (2003)
  * (4) D. Aharonov and M. Ben-Or, Polynomial simulations of decohered quantum computers. 37th Annual Symposium on Foundations of Computer Science (FOCS) pp 46–55, (1996)
  * (5) S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits. Phys. Rev. A 70 (5): 052328, (2004).
  * (6) E. Knill, Fault-Tolerant Postselected Quantum Computation: Schemes. arXiv:quant-ph/0402171
  * (7) S. Bravyi and A. Kitaev, Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A 71, 022316, (2005).
  * (8) H. Barnum, E. Knill, G. Ortiz, and L. Viola, Generalizations of entanglement based on coherent states and convex sets. Phys. Rev. A 68, 032308 (2003); H. Barnum, E. Knill, G. Ortiz, R. Somma, and L. Viola, A Subsystem-Independent Generalization of Entanglement. Phys. Rev. Lett. 92, 107902 (2004); A. Klyachko, Coherent states, entanglement, and geometric invariant theory. arXiv:quant-ph/0206012.
  * (9) K. S. Gibbons, M. J. Hoffman, and W. K. Wootters, Discrete phase space based on finite fields. Phys. Rev. A 70, 062101 (2004); D. Gross, Hudson’s theorem for finite-dimensional quantum systems. J. Math. Phys., 47(12):122107, (2006);
  * (10) J. Barrett, Information processing in generalized probabilistic theories. Phys. Rev. A 75, 032304 (2007); L. Hardy, Quantum Theory From Five Reasonable Axioms. quant-ph/0101012 (2001); A. S. Holevo, “Probabilistic and Statistical Aspects of Quantum Theory”, North Holland (1982); S Popescu and D Rohrlich, Quantum nonlocality as an axiom. Foundations of Physics, 24, 379, (1994).
  * (11) Barrett, J., de Beaudrap, N., Hoban, M.J., and Lee, C., The computational landscape of general physical theories. NPJ Quantum Inf 5, 41 (2019).
  * (12) N. Ratanje and S. Virmani, Generalized state spaces and nonlocality in fault-tolerant quantum-computing schemes. Phys. Rev. A 83 032309 (2011)
  * (13) N. Ratanje and S. Virmani, Exploiting non-quantum entanglement to widen applicability of limited-entanglement classical simulations of quantum systems. arXiv:1201.0613v1.
  * (14) H. Anwar, S Jevtic, O. Rudolph, and S. Virmani, Families of pure PEPS with efficiently simulatable local hidden variable models for most measurements. arXiv:1412.3780v2
  * (15) H. Anwar, S Jevtic, O. Rudolph, and S. Virmani, Smallest disentangling state spaces for general entangled bipartite quantum states. New J. Phys. 17 093047 (2015); H. Anwar, S Jevtic, O. Rudolph, and S. Virmani, Generalised versions of separable decompositions applicable to bipartite entangled quantum states. New J. Phys. 21 093031 (2019)
  * (16) O. Rudolph, A separability criterion for density operators, J. Phys. A: Math. Gen. 33 3951 (2000); O. Rudolph, A new class of entanglement measures, J. Math. Phys. 42 5306 (2001)
  * (17) F. Verstraete and J.I. Cirac, Valence-bond states for quantum computation. Phys. Rev. A 70, 060302(R) (2004).
  * (18) R F Werner, Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model. Phys. Rev. A 40 4277 (1989)
  * (19) D. Avis, Polyhedral Computation (lecture notes) - Lecture 2. http://www.lab2.kuis.kyoto-u.ac.jp/ avis/courses/pc/2010/notes/lec2.pdf
  * (20) Barrett, S., Bartlett, S., Doherty, A., Jennings, D. & Rudolph, T. Transitions in the computational power of thermal states for measurement-based quantum computation. Physical Review A. 80, 062328 (2009)
  * (21) Browne, D., Elliott, M., Flammia, S., Merkel, S., Miyake, A. & Short, A. Phase transition of computational power in the resource states for one-way quantum computation. New Journal Of Physics. 10, 023010 (2008)
  * (22) A. Peres, . Separability Criterion for Density Matrices. Phys. Rev. Lett. 77 (8): 1413 (1996); M. Horodecki, P. Horodecki, and R. Horodecki, Separability of mixed states: necessary and sufficient conditions. Phys. Lett. A. 223 (1–2): 1–8. (1996)
  * (23) Mora, C., Piani, M., Miyake, A., Van den Nest, M., Dür, W. & Briegel, H. Universal resources for approximate and stochastic measurement-based quantum computation. Physical Review A. 81, 042315 (2010)
  * (24) B. Terhal and D. DiVincenzo, Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games. Quant. Inf. Comp. Vol. 4 (No. 2), pages 134–145 (2004)
  * (25) Harrow, A. & Montanaro, A. Quantum computational supremacy. Nature. 549, 203-209 (2017)
  * (26) Bremner, M., Jozsa, R. & Shepherd, D. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings Of The Royal Society A: Mathematical, Physical And Engineering Sciences. 467, 459-472 (2011)
  * (27) Bremner, M., Montanaro, A. & Shepherd, D. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters. 117, 080501 (2016)
  * (28) Aaronson, S. & Chen, L. Complexity-theoretic foundations of quantum supremacy experiments. Proc. 32 Comput. Complex. Conf., CCC ’17 (2017)
  * (29) Bremner, M., Montanaro, A. & Shepherd, D. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum. 1 pp. 8 (2017)
  * (30) Miller, J., Sanders, S. & Miyake, A. Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification. Physical Review A. 96, 062320 (2017)
  * (31) Gao, X., Wang, S. & Duan, L. Quantum supremacy for simulating a translation-invariant Ising spin model. Physical Review Letters. 118, 040502 (2017)
  * (32) Yoganathan, M., Jozsa, R. & Strelchuk, S. Quantum advantage of unitary Clifford circuits with magic state inputs. Proceedings Of The Royal Society A. 475, 20180427 (2019)
  * (33) Haferkamp, J., Hangleiter, D., Bouland, A., Fefferman, B., Eisert, J. & Bermejo-Vega, J. Closing gaps of a quantum advantage with short-time Hamiltonian dynamics. Physical Review Letters. 125, 250501 (2020)
  * (34) R. Jozsa and N. Linden, On the role of entanglement in quantum-computational speed-up. Proc. Roy. Soc. A, 459 2036 (2003).
  * (35) G. Vidal, Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett. 91 147902, (2003)
  * (36) M. A. Nielsen, Cluster-state quantum computation. Rep. Math. Phys. 57 147–61 (2006).
  * (37) N. Yoran and A. J. Short, Classical Simulation of Limited-Width Cluster-State Quantum Computation. Phys. Rev. Lett. 96, 170503 (2006)
  * (38) I. L. Markov and Y. Shi, Simulating Quantum Computation by Contracting Tensor Networks. SIAM Journal on Computing, 38(3):963-981, (2008).
  * (39) S Bravyi, D Gosset, R König, and M Tomamichel, Quantum advantage with noisy shallow circuits in 3D. Nature Physics 16 (10), 1040-1045, 2020.
  * (40) Jozsa, R. & Miyake, A. Matchgates and classical simulation of quantum circuits. Proceedings Of The Royal Society A: Mathematical, Physical And Engineering Sciences. 464, 3089-3106 (2008)
  * (41) Jozsa, R. & Van den Nest, M. Classical simulation complexity of extended Clifford circuits. Quantum Info. Comput., 14, pp. 633–648, (2014).
  * (42) S. Virmani, S. F. Huelga, and M. B. Plenio, Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71, 042328 (2005).
  * (43) Napp, J., La Placa, R., Dalzell, A., Brandao, F. & Harrow, A. Efficient classical simulation of random shallow 2D quantum circuits. ArXiv Preprint ArXiv:2001.00021. (2019)
  * (44) Noh, K., Jiang, L. & Fefferman, B. Efficient classical simulation of noisy random quantum circuits in one dimension. Quantum. 4 pp. 318 (2020)
  * (45) Okay, C., Zurel, M. & Raussendorf, R. On the extremal points of the $\Lambda$ -polytopes and classical simulation of quantum computation with magic states. Quantum Info. and Comput. 21 No.13 & 14, 1533-7146 (2021)
  * (46) Pashayan, H., Reardon-Smith, O., Korzekwa, K. & Bartlett, S. Fast estimation of outcome probabilities for quantum circuits. Quantum 5, 606 (2021)
  * (47) Gosset, D., Grier, D., Kerzner, A. & Schaeffer, L. Fast simulation of planar Clifford circuits. ArXiv Preprint ArXiv:2009.03218. (2020)
  * (48) Van den Nest, M. Universal quantum computation with little entanglement. Physical Review Letters. 110, 060504 (2013)
  * (49) Qassim, H., Pashayan, H. & Gosset, D. Improved upper bounds on the stabilizer rank of magic states. ArXiv Preprint ArXiv:2106.07740. (2021)
  * (50) Raussendorf, R., Bermejo-Vega, J., Tyhurst, E., Okay, C. & Zurel, M. Phase-space-simulation method for quantum computation with magic states on qubits. Physical Review A. 101, 012350 (2020)
  * (51) Schwarz, M. & Van den Nest, M. Simulating quantum circuits with sparse output distributions. ArXiv Preprint ArXiv:1310.6749. (2013)
  * (52) Seddon, J., Regula, B., Pashayan, H., Ouyang, Y. & Campbell, E. Quantifying quantum speedups: Improved classical simulation from tighter magic monotones. PRX Quantum. 2, 010345 (2021)
  * (53) H. Pashayan, J. J. Wallman, and S. D. Bartlett, Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities. Phys. Rev. Lett. 115, 070501 (2015)
  * (54) Van den Nest, M. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quant. Inf. Comp. 10, 3-4 pp. pp0258-0271 (2010)
  * (55) Van den Nest, M., Dür, W., Vidal, G. & Briegel, H. Classical simulation versus universality in measurement-based quantum computation. Physical Review A. 75, 012337 (2007)
  * (56) Zurel, M., Okay, C. & Raussendorf, R. Hidden Variable Model for Universal Quantum Computation with Magic States on Qubits. Physical Review Letters. 125, 260404 (2020)
  * (57) Gross, D., Eisert, J., Schuch, N. & Perez-Garcia, D. Measurement-based quantum computation beyond the one-way model. Physical Review A. 76, 052315 (2007)
  * (58) M. Van den Nest, A. Miyake, W. Dür, H. J. Briegel, Universal Resources for Measurement-Based Quantum Computation. Phys. Rev. Lett. 97, 150504 (2006).
  * (59) Jozsa, R. On the simulation of quantum circuits. ArXiv Preprint Quant-ph/0603163. (2006)
  * (60) F. Verstraete, M. Popp, and J. I. Cirac, Entanglement versus Correlations in Spin Systems. Phys. Rev. Lett. 92, 027901 (2004)
  * (61) A. Kissinger, J. van de Wetering, Universal MBQC with generalised parity-phase interactions and Pauli measurements. Quantum 3, 134 (2019)
  * (62) Y. Takeuchi, T. Morimae, M. Hayashi, Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements. Sci Rep. 9, 13585 (2019)
  * (63) J. Miller, A. Miyake, Hierarchy of universal entanglement in 2D measurement-based quantum computation. npj Quantum Information 2, 16036 (2016); M. Gachechiladze, O. Gühne, A. Miyake, Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states. Phys. Rev. A, 99, 052304 (2019)
  * (64) D. L. Zhou, B. Zeng, Z. Xu, and C. P. Sun, Quantum computation based on d-level cluster state. Phys. Rev. A 68, 062303 (2003); W. Hall, Cluster state quantum computation for many-level systems. Quant. Inf. & Comp., 7, Issue 3 pp 184–208 (2007)
  * (65) L. P. Hughston, R. Jozsa, and W. K. Wootters, A complete classification of quantum ensembles having a given density matrix. Phys. Lett. A 183, 1, P.14-18 (1993).
  * (66) H. Pashayan, S Bartlett, and D. Gross, From estimation of quantum probabilities to simulation of quantum circuits. Quantum 4, 223 (2020).
  * (67) L. Gurvitz and H. Barnum, Largest separable balls around the maximally mixed bipartite quantum state. Phys. Rev. A, 66, 062311 (2002)
  * (68) B. Terhal, Bell inequalities and the separability criterion. Phys. Lett. A, 271, 319 (2000).
  * (69) M. Van den Nest, Simulating quantum computers with probabilistic methods. Quant. Inf. Comp. 11, 9-10 pp. 784-812 (2011)
  * (70) H. J. Garcia, I. L. Markov, and A. W. Cross. Efficient inner-product algorithm for stabilizer states. arXiv preprint arXiv:1210.6646, (2012); S. Bravyi, G. Smith, and J. A. Smolin, Trading classical and quantum computational resources. Physical Review X, 6:021043, (2016).
  * (71) H. Buhrman, R. Cleve, M. Laurent, N. Linden, A. Schrijver, and F. Unger, New limits on fault-tolerant quantum computation. Proc. of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (IEEE, New York, 2006), pp. 411–419.
  * (72) L. G. Valiant, Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31(4):1229–1254, (2002).
  * (73) B. M. Terhal and D. P. DiVincenzo, Classical simulation of noninteracting-fermion quantum circuits. Phys. Rev. A, 65(3):032325, (2002).
  * (74) M. B. Hastings, An area law for one dimensional quantum systems. J. Stat. Mech., 2007:08024, (2007).
  * (75) E. F. Galvao, Discrete Wigner functions and quantum computational speedup. Phys. Rev. A 71, 042302 (2005); C. Cormick, E. F. Galvao, D. Gottesman, J. P. Paz, and A. O. Pittenger, Classicality in discrete Wigner functions, Phys. Rev. A 73 012301 (2006).
  * (76) D. J. Brod, Efficient classical simulation of matchgate circuits with generalized inputs and measurements. Phys. Rev. A 93, 062332 (2016)
  * (77) Arute et. al., Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019.
  * (78) R. Raz, Exponential separation of quantum and classical communication complexity. Proc. 31st Annual ACM Symp. Theory of Computing, pages 358–367, (1999).
  * (79) F Pan, K Chen and P Zhan, Solving the sampling problem of the sycamore quantum circuits. Phys. Rev. Lett. 129 (9), 090502 (2022).
  * (80) D. Aharonov, X. Gao, Z. Landau, Y. Liu, and U. Vazirani. A polynomial-time classical algorithm for noisy random circuit sampling. arXiv:2211.03999, (2022).
  * (81) S. Popescu and D. Rohrlich, Generic quantum nonlocality. Phys. Lett. A 166, 293 (1992).
  * (82) R. Somma, H. Barnum, G. Ortiz, and E. Knill, Efficient Solvability of Hamiltonians and Limits on the Power of Some Quantum Computational Models. Phys. Rev. Lett. 97, 190501 (2006)