Proof Clearly $(i, v_i) \in \Gamma [v, w_0]$ for all i, so suppose $(i, j)$ is sandwiched by a noninversion $\langle k, l \rangle $ of v. We will produce a permutation $w>v$ sending i to j, which shows that $(i, j) \in \Gamma [v, w_0]$ . Let $a=v^{-1}(j)$ . If $a, i$ form a noninversion of v, then $v\cdot (a~i)>v$ (where $(a~i)$ is the transposition sending a to i and vice versa) and $v \cdot (a~i)$ sends i to j. If $a, i$ is an inversion, then $v \cdot (i~k) \cdot (i~a)>v$ if $i < a$ and $v\cdot (i~l) \cdot (i~a) > v$ if $i > a$ . These permutations send i to j, so we are done.

To show that the above description gives all elements of $ \Gamma [v, w_0]$ , suppose that $\langle a, b \rangle $ is a noninversion of v such that $\ell (v \cdot (a~b))=\ell (v)+1$ . The graph of $v \cdot (a~ b)$ can be obtained from $\Gamma (v)$ by applying the following move: look at the rectangle bounded by $(a, v_a)$ and $(b, v_b)$ , and replace $(a, v_a)$ and $(b, v_b)$ with the other corners of the rectangle, $(a, v_b)$ and $(b, v_a)$ . Notice that $(a, v_b)$ and $(b, v_a)$ are sandwiched by the noninversion $\langle a, b \rangle $ . Furthermore, if $(i, j)$ is sandwiched by a noninversion of $v \cdot (a~b)$ , then it is also sandwiched by a noninversion of v. Thus, repeating this move produces graphs whose points are sandwiched by some noninversion of v. Because, for arbitrary $u>v$ , the graph of u can be obtained from that of v by a sequence of these moves, we are done.▪

Proof Notice that, by definition,

(3.2) $$ \begin{align} \det(M|_{\Gamma[v, w_0]})= \sum_{\substack{w \in S_n \\ \Gamma(w)\subseteq \Gamma[v, w_0]}} (-1)^{\ell(w)}~m_{1, w(1)} \cdots m_{n, w(n)}. \end{align} $$

We show that this sum is in fact over $[v, w_0]$ . Lemma 3.2 shows that for arbitrary $v \in S_n$ , $\{w: \Gamma (w) \subseteq \Gamma [v, w_0]\}$ are the permutations in what Sjöstrand calls the “left convex hull” of v. Applying [Reference SjöstrandS07, Theorem 4], we obtain that $\{w \in S_n: \Gamma (w) \subseteq \Gamma [v, w_0]\}=[v, w_0]$ as desired.▪

Proof By Lemma 3.1, we have

(3.4) $$ \begin{align} \operatorname{Imm}_v(M)= (-1)^{\ell(v)} \sum_{w \geq v} (-1)^{\ell(w)} ~m_{1, w(1)} \cdots m_{n, w(n)}. \end{align} $$

Notice that v also avoids 24153, 31524, and 426153, because the occurrence of any of those patterns would imply an occurrence of 2143. So, by Proposition 3.3, the right-hand side of (3.4) is equal to $(-1)^{\ell (v)} \det (M|_{\Gamma [v, w_0]})$ .▪

Proof Let Q be a square of size $k+1$ in $\Gamma [v, w_0]$ . Note that Q is sandwiched by some noninversion $\langle i, j \rangle $ of v. Indeed, let $(r_1, c_1)$ be the northwest corner of Q, and let $(r_2, c_2)$ be the southeast corner. Then, $(r_1, c_1)$ is either sandwiched by a noninversion $\langle i, \ell \rangle $ or is equal to $(i, v_i)$ for some i. In particular, $(i, v_i)$ is weakly northwest of $(r_1, c_1)$ . Similarly, we can find j, so that $(j, v_j)$ is weakly southeast of $(r_2, c_2)$ . So, the noninversion $\langle i, j \rangle $ sandwiches every point in Q. On the other hand, the rectangle with corners $(i, v_i), (j, v_i), (i, v_j), (j, v_j)$ uses $j-i+1$ columns and $v_j-v_i+1$ rows. So, both $j-i+1$ and $v_j-v_i+1$ must be at least $k+1$ , which shows one direction. The other direction is straightforward.▪

Proof Suppose $i_1< i_2< \cdots < i_{k+1}$ and $v_{i_1}< v_{i_2}< \cdots < v_{i_{k+1}}$ . In other words, $v_{i_1},v_{i_2},...,v_{i_{k+1}}$ is an occurrence of the pattern $12...(k+1)$ . Let R be the rectangle with corners at $(i_1,v_{i_1})$ , $(i_1, v_{i_{k+1}})$ , $(i_{k+1}, v_{i_{k+1}})$ , and $(i_{k+1}, v_{i_1})$ . Notice that R is at least of size $(k+1)\times (k+1)$ . For all $(r, c) \in R$ , $(r, c)$ is sandwiched by $\langle i_1, i_{k+1} \rangle $ , a noninversion. By Lemma 3.2, this means $(r, c)$ is in $\Gamma [v, w_0]$ . So, all of R is in $\Gamma [v, w_0]$ and there is a square of size $k+1$ in $\Gamma [v, w_0]$ . By Lemma 4.1, this means there is some noninversion $\langle i,j\rangle $ where $j-i>k$ or $v_j-v_i>k$ .▪

Proof By Lemma 4.1, $\Gamma [v, w_0]$ contains a square of size $k+1$ if and only if, for some noninversion $\langle i, j \rangle $ , $j-i \geq k$ and $v_j-v_i \geq k$ . We will show that the existence of such an inversion is equivalent to the statement about patterns in the proposition.

Suppose for some noninversion $\langle i, j \rangle $ of v, $j-i \geq k$ and $v_j-v_i \geq k$ . Now, take

$$ \begin{align*}L:= \{v_i +1, \dots, v_j-1\} \cap \{v_{i+1}, \dots,v_{j-1}\}. \end{align*} $$

If L has at least $k-1$ elements, let $S=T$ be any $(k-1)$ -element subset of L. Otherwise, let S be any $(k-1)$ -element subset of $\{v_i +1, \dots , v_j-1\}$ containing L and let T be any $(k-1)$ -element subset of $\{v_{i+1}, \dots ,v_{j-1}\}$ containing L. Notice that $S \cup T$ contains exactly $k-1$ numbers between $v_i$ and $v_j$ and exactly $k-1$ numbers that lie to the right of $v_i$ and to the left of $v_j$ in v. Now, we consider the pattern formed by $ S \cup T \cup \{v_i, v_j\}$ in v; say this pattern is $u_1 \dots u_m$ . By construction, m is between $k+1$ and $2k$ . Say $u_r$ corresponds to $v_i$ . By construction, $u_{r+k}$ corresponds to $v_j$ and $u_{r+k}-u_r=k$ .

Now, let $u_1 \dots u_m$ with $k+1 \leq m \leq 2m$ be a pattern such that $u_{r+k}-u_r=k$ for some r. If this pattern appears in v, let $v_i$ correspond to $u_r$ and $v_j$ correspond to $u_{r+k}$ . Note that $\langle i, j \rangle $ is a noninversion of v. To pass from u to v, we insert additional numbers and increase existing ones, so $j-i \geq k$ and $v_j - v_i \geq k$ .▪

Proof Let Q be a square of size r in $\Gamma [v, w_0]$ . Without loss of generality, Q lies on or above the antidiagonal (the argument is analogous if the northeast corner of Q lies on or below the antidiagonal). Then, by Lemma 3.2, the northwest corner of Q is either $(i,v_i)$ or it is sandwiched by some noninversion $\langle i,j\rangle $ . In either case, $\mathbf {B}_{i,v_i}$ contains all of Q. Because $\mathbf {B}_{i,v_i}$ is either a bounding box or contained in a bounding box, Q must be contained in a single bounding box.

Now, we can assume Q is contained within the bounding box $\mathbf {B}_{i,v_i}$ . If $\mathbf {B}_{i,v_i}$ is blue, then there is some $(j,v_j)\in \Gamma (v)$ such that either $(j,v_j)$ is the southeast corner Q or $\langle i,j\rangle $ is a noninversion that sandwiches all of Q. Consider the square of size r with northwest corner $(i,v_i)$ . Everything in this square is in $\Gamma (v)$ or is sandwiched by $\langle i,j\rangle $ . Thus, by Lemma 3.2, this square is in $\Gamma [v, w_0]$ . Similarly, if the bounding box is red, then the square of size r with southeast corner $(i,v_i)$ is in $\Gamma [v, w_0]$ .▪

Proof Suppose $v\in S_n$ avoids 1324 and 2143 and $\Gamma [v, w_0]$ contains a square of size $k+1$ . Then, by Proposition 5.3, $\Gamma [v, w_0]$ contains a square of size $k+1$ that has a spanning corner as either its most northwestern or most southeastern box. From the proof of Proposition 4.1, this means there is a square of size $k+1$ in $\Gamma [v, w_0]$ sandwiched by the noninversion $\langle i,j\rangle $ with either i or j a spanning corner. Let $u=u_1\dots u_m$ be the pattern constructed in Proposition 5.2 with $u_{\ell +k}-u_\ell =k$ . If i is a spanning corner, then $\ell =1$ and $u_\ell =1$ , and if j is a spanning corner, then $\ell +k=m$ and $u_{\ell +k}=m$ .

Thus, if v avoids 1324 and 2143 as well as all patterns u of length $k+1\leq m\leq 2k$ where $u_1=1$ and $u_{k+1}=k+1$ or where $u_m=m$ and $u_{m-k}=m-k$ , then $\Gamma [v, w_0]$ contains no square of size $k+1$ . By Theorem 4.2, $\operatorname {Imm}_v$ is k-positive.▪

Question 6.1 Suppose some finite subset S of the dual canonical basis is positive on $M \in G$ . Which other elements of the dual canonical basis are positive on M? In particular, what if S consists of the generalized minors corresponding to the first k fundamental weights and their images under the Weyl group action?

Question 6.2 When is $\operatorname {Imm}_v$ a cluster monomial in $\mathcal {O}(GL_n({\mathbb C}))$ ? When is $\operatorname {Imm}_v$ a cluster monomial in a k-positivity cluster subalgebra from [Reference Brosowsky, Chepuri and MasonB17]?

Proof This follows immediately from the fact that left multiplication by $w_0$ is an antiautomorphism of the Bruhat order.▪

Proof Suppose $w^{-1}(i)=w_i$ , and let t be the transposition sending i to $w_i$ , $w_i$ to i, and fixing everything else. We can assume that $i< w_i$ . We compare w and t in the Bruhat order by comparing $w[j]$ and $t[j]$ for $j \in [n]$ .

For two subsets $I=\{i_1< \dots < i_r\}$ , $K=\{k_1< \dots < k_r\}$ , we say $I \leq J$ if $i_j\leq k_j$ , for all $j \in [r]$ . For two permutations $v, w \in S_n$ , we have $v \leq w$ if and only if for all $j \in [n]$ , $v[j] \leq w[j]$ [Reference Björner and BrentiBB05, Theorem 2.6.1].

For $j< i$ and $j\geq w_i$ , $t[j]=[1, j]$ , and so clearly $t[j]\leq w[j]$ . For $i \leq j < w_i $ , $t[j]=[1, i-1] \cup [i+1, j] \cup \{w_i\}$ . Let $t[j]=\{a_1 < a_2 < \cdots < a_j\}$ and $w[j]=\{b_1 < b_2 < \cdots < b_j\}$ . Notice that $a_j=w_i$ and $w_i \in w[j]$ , so we definitely have that $a_j \leq b_j$ . For the other inequalities, suppose $w[j] \cap [1, i]=\{b_1, \dots , b_r\}$ . Because i is not in $w[j]$ , $r \leq i-1$ . This implies that $b_k \leq a_k$ , for $k \leq r$ . It also implies that $a_{r+k} \leq i+k$ and $b_{r+k} \geq i+k$ , for $r+k < j$ , which establishes the remaining inequalities. Thus, $w \geq t$ .

Because $w \geq t$ , every reduced expression for w has a reduced expression for t as a subexpression. Thus, Proposition 7.6 implies t must have a reduced expression in which each simple transposition appears once.

Now, t has a reduced expression which is a palindrome; it is length $2c+1$ and contains at most $c+1$ simple transpositions. Every reduced expression of t has the same length and contains the same set of simple transpositions. So, if $c>0$ , in each reduced expression, some simple transposition appears twice. We conclude that $\ell (t)=1$ and $|i -w_i|=1$ .▪

Proof If a bounding box $B_{i, w_i}$ is green, then by definition $i=w_i$ . The corner $(i, i)$ has maximal span, which implies there are no $(j, w_j)$ with $j < i$ and $w_j > i$ . In other words, $w[i-1]=[i-1]$ , which would contradict the assumption that w is not contained in a maximal parabolic subgroup.

There are also no spanning corners of the form $(i, i+1)$ . Indeed, if $(i, i+1)$ were a spanning corner, then there are no $(j, w_j)$ with $j\leq i-1$ and $w_j>i+1$ or with $j\geq i+1$ and $w_j\leq i-1$ . The latter implies that $w_{i+1}=i$ , which, together with the first inequality, implies $w[i-1]=[i-1]$ , a contradiction. By Lemma 7.7, if a bounding box $B_{i, w_i}$ is purple, then $|i-w_i|=1$ . This implies a spanning chord of the form $(k, k+1)$ , which is impossible, so there are no purple bounding boxes.

So, all bounding boxes are either blue or red. Suppose the bounding box $B_{i, w_i}$ is followed by $B_{j, w_j}$ in the ordering specified in the proposition. We suppose for the sake of contradiction that they are the same color. Without loss of generality, we may assume that they are blue, so $i< w_i$ and $j< w_j$ . Otherwise, we consider $w^{-1}$ instead of w. (By Proposition 7.6, $w^{-1}$ is also 321- and 3412-avoiding. The span of $(i, w_i)$ and $(w_i, w^{-1}(w_i))$ are the same, so the bounding boxes of $\Gamma [e, w^{-1}]$ are the same as the bounding boxes of $\Gamma [e, w]$ , but with opposite color.)

Because $B_{j, w_j}$ follows $B_{i, w_i}$ , there are no pairs $(k, w_k)$ with $k< j$ and $w_i< w_k$ . Indeed, such a pair is spanned by neither $(i, w_i)$ nor $(j, w_j)$ , so its existence would imply the existence of a bounding box between $B_{i, w_i}$ and $B_{j, w_j}$ or enclosing one of them, both of which are contradictions. In other words, $w[j-1] \subseteq [w_i]$ , so we must have $j-1 \leq w_i$ . If $j=w_i+1$ , then $w[w_i] \subseteq [w_i]$ , a contradiction. So, we have $i < j \leq w_i < w_j$ .

Now, consider the reduced expression for w obtained by starting at the identity, moving $w_1$ to position 1 using right multiplication by $s_a$ ’s, then moving $w_2$ to position 2 (if it is not already there) using right multiplication, etc. Note that when $w_k$ is moved to position k, no numbers greater than $w_k$ have moved. In addition, once $w_k$ is in position k, it never moves again. Suppose $w_{i-1}$ has just moved to position $i-1$ . Because $(i, w_i)$ is a spanning corner, we have not moved any numbers larger than $w_i$ . In other words, k is currently in position k for $k \geq w_i$ ; in particular, $w_i$ is in position $w_i$ . Now, to move $w_i$ to position i, we must use the transpositions $s_{w_i-1}, s_{w_i -2}, \dots , s_{i+1}, s_i$ in that order. By Proposition 7.6, each simple transposition can only be used once in this reduced expression for w. Thus, these simple transpositions have not been used before we move $w_i$ to position i, so in fact k is in position k for $k>i$ before we move $w_i$ to position i.

Now, we move $w_i$ to position i. Because $s_{w_i-1}, \dots , s_i$ will never be used again in the expression for w, we conclude that $w_{i+1}, \dots , w_{w_i-1}$ are already in positions $i+1, \dots , w_i -1$ . Note also that the number currently in position $w_i$ is $w_i-1$ , because $|i-w_i|>1$ .

Because $w_j>w_i$ , $w_j$ is not yet in position j. This implies that $j \geq w_i$ . We already had that $j \leq w_i$ , so in fact they are equal. So, after $w_i$ has moved to position i, $w_j$ is the next number not yet in the correct position. Recall that for $k>w_i$ , k is still in position k. So, to move $w_j$ to position $w_i$ , we use $s_{w_j}, s_{w_j-1}, \dots , s_j$ in that order (because $|j-w_j|>1$ , $s_{j+1}$ is on this list of transpositions). Notice that the number in position j, which is $w_i-1$ , moves to position $j+1$ . We cannot use $s_j$ or $s_{j+1}$ again, so $w_i-1$ must be $w_{j+1}$ . However, the pair $(j+1, w_i-1)$ satisfies $j+1>j$ and $w_i-1< w_i$ , so it is spanned by neither $(i, w_i)$ nor $(j, w_j)$ . Say $(j+1, w_i-1)$ is spanned by the spanning corner $(a, w_a)$ . Then, $(a, w_a)$ spans neither of $(i, w_i), (j, w_j)$ , which implies $i < \min (a, w_a) < j < \max (a, w_a)< w_j$ . This means exactly that the bounding box order is $B_{i, w_i}, B_{a, w_a}, B_{j, w_j}$ , a contradiction.▪

Proof Let $\alpha _a$ denote the inverse of $\delta _a$ , so that w sends $\alpha _i(j)$ to $\alpha _{u_i}(w_j)$ (because $(i, w_i)$ is a noncorner, $i, w_i \neq n$ and this is well defined). Note that $\delta _a$ and $\alpha _a$ are order-preserving. Let $\delta :=\delta _i \times \delta _{w_i}$ and $\alpha :=\alpha _i \times \alpha _{w_i}$ .

We first show that $\delta $ is a bijection from the noncorner pairs $(j, w_j)$ of $\Gamma [e, w]$ with $j \neq i$ to the noncorner pairs $(k, u_k)$ of $\Gamma [e, u]$ . Recall that $(j, w_j)$ is a noncorner of $\Gamma [e, w]$ if and only if $(j, w_j)$ is sandwiched by an inversion of w. Moreover, every noncorner pair $(j, w_j)$ is sandwiched by an inversion $\langle k, l \rangle $ where $(k, w_k)$ and $(l, w_l)$ are corners of $\Gamma [e, w]$ . Indeed, choose the smallest k such that $\langle k, j \rangle $ is an inversion and the largest l such that $\langle j, l \rangle $ is an inversion. Then, $(k, w_k)$ and $(l, w_l)$ are both corners.

Let $j \neq i$ and suppose $(j, w_j)$ is sandwiched by an inversion $\langle k, l \rangle $ of w. We can choose $k, l$ , so that $(k, w_k)$ and $(l, w_l)$ are corners of $\Gamma [e, w]$ ; in particular, neither is equal to i. Because $\delta _a$ is order-preserving, $\langle \delta _i(k), \delta _i(l) \rangle $ is an inversion of u and sandwiches $\delta (j, w_j)$ . Similarly, if $(j, u_j)$ is sandwiched by an inversion $\langle k, l \rangle $ of u, then $\alpha (j, u_j)$ is sandwiched by the inversion $\langle \alpha _i(k), \alpha _i(l) \rangle $ of w. As $\delta $ and $\alpha $ are inverses, we are done.

This also implies that $\delta $ is a bijection from the corner pairs $(j, w_j)$ of $\Gamma [e, w]$ to the corner pairs $(k, u_k)$ of $\Gamma [e, u]$ .

Next, we show that $\delta $ respects containment of spans for corner pairs of w.

Suppose $\sigma (k, w_k)$ is contained in $\sigma (j, w_j)$ and both pairs are corners of $\Gamma [e, w]$ . We may assume that $k \neq j$ (otherwise, $\delta $ clearly respects containment of spans) and that $j < w_j$ (otherwise, we can consider instead $w^{-1}$ , which avoids 3412 also, and $u^{-1}$ ). By assumption, $k, w_k \in [j, w_j]$ , so $\delta _i(k)$ and $\delta _{w_i}(w_k)$ are in $[j-1, w_j]$ . We have

$$ \begin{align*}\sigma(\delta_i(j), \delta_{w_i}(w_j))= \left\{\begin{array}{@{}llr} [j, w_j] & \text{ if }j < i, w_j < w_i, & \quad\quad\text{(Case I)}\cr [j, w_j-1] & \text{ if }j < i, w_j > w_i, & \quad\quad\text{(Case II)}\cr [j-1, w_j] & \text{ if }j > i, w_j < w_i, & \quad\quad\text{(Case III)}\cr [j-1, w_j-1] & \text{ if }j > i, w_j > w_i. & \quad\quad\text{(Case IV)} \end{array}\right. \end{align*} $$

Case I: The only way $\sigma (\delta (j, w_j))$ could fail to contain $\sigma (\delta (k, w_k))$ here is if $j-1 \in \{\delta _i(k),\delta _{w_i}(w_k)\}$ . If $j-1=\delta _i(k)$ , then $k=j$ , a contradiction. If $j-1=\delta _{w_i}(w_k)$ , then $w_k=j$ and $w_k > w_i$ . But $w_k< w_j$ and $w_j< w_i$ by assumption, so we reach a contradiction.

Case II: The only way $\sigma (\delta (j, w_j))$ could fail to contain $\sigma (\delta (k, w_k))$ here is if $j-1$ or $w_j$ is in $ \{\delta _i(k),\delta _{w_i}(w_k)\}$ . We will show that $w_j$ is not in $\{\delta _i(k),\delta _{w_i}(w_k)\}$ by contradiction; the other case is similar.

Suppose $w_j \in \{\delta _i(k),\delta _{w_i}(w_k)\}$ . Because $w_k < w_j$ , we must have $w_j=\delta _i(k)$ , which means $k=w_j$ and $k< i$ . Notice that $\langle j, k \rangle $ is an inversion of w, as is $\langle j, i \rangle $ . Because $(k, w_k)$ is not sandwiched by any inversions of w, we must have $w_k< w_i$ . To summarize, $j< k< i$ and $w_k< w_i< w_j$ . This means $w_j w_k w_i$ form a 312 pattern in w.

Note that w cannot have any inversions $\langle a, j \rangle $ or $\langle k, a \rangle $ , because this would result in $(j, w_j)$ or $(k, w_k)$ , respectively, being sandwiched by an inversion. We further claim that if a forms an inversion with k and i, then it must also form an inversion with j. Indeed, if a forms an inversion with k and i, then $a< k< i$ and $w_a>w_i>w_k$ . If $j< a$ and $w_j< w_a$ , then $w_j w_a w_k w_i$ form a 3412 pattern; similarly if $j>a$ and $w_j>w_a$ .

Consider $a< j$ . From above, we know that $\langle a, j \rangle $ is not an inversion. If $w_a>w_i$ , then $\langle a, i \rangle $ and $\langle a, k \rangle $ are both inversions. This combination is impossible, so $w[j-1] \subseteq [w_i-1]$ . In addition, any $a \in [j+1, k-1]$ with $w_a>k$ forms an inversion with k and i but not j, which is impossible. So, $w[j+1, k-1] \subseteq [k]$ . Because $w_j=k$ and $w_k< w_i< k$ , we conclude $w[k] = [k]$ . But $i>k$ and $w_i< k$ , a contradiction.

Case III: The span of $\delta (k, w_k)$ is contained in $[j-1, w_j]$ by assumption.

Case IV: The only way $\sigma (\delta (j, w_j))$ could fail to contain $\sigma (\delta (k, w_k))$ here is if $w_j \in \{\delta _i(k),\delta _{w_i}(w_k)\}$ . The argument that this cannot happen is similar to Case I; we leave it to the reader.

Finally, we will show that $\alpha $ respects span containment for corner pairs of u. This completes the proof of (1): suppose $(j, w_j)$ is a spanning corner of $\Gamma [e, w]$ and $\sigma (\delta (j, w_j)) \subseteq \sigma ((a, u_a))$ for a spanning corner $(a, u_a)$ . Note that $\delta (j, w_j)$ is a corner. Because $\alpha $ respects span containment for corners, $\sigma (j, w_j) \subseteq \sigma (\alpha (a, u_a))$ . By maximality of $\sigma (j, w_j)$ , we have $\sigma (j, w_j)=\sigma (\alpha (a, u_a))$ . In particular, $\sigma (\alpha (a, u_a)) \subseteq \sigma (j, w_j)$ , so because $\delta $ preserves span containment for corners, the span of $(a, u_a)$ is contained in the span of $\delta (j, w_j)$ . So, $\delta (j, w_j)$ is a spanning corner of $\Gamma [e, u]$ . Reversing the roles of w and u in the above argument shows that $\alpha (j, u_j)$ is a spanning corner of $\Gamma [e, w]$ if $(j, u_j)$ is a spanning corner of $\Gamma [e, u]$ . So, $\delta $ is a bijection between the spanning corners of $\Gamma [e, w]$ and the spanning corners of $\Gamma [e, u]$ .

Suppose $\sigma (k, u_k)$ is contained in $\sigma (j, u_j)$ and both pairs are corners of $\Gamma [e, u]$ . Again, we may assume that $k \neq j$ (otherwise, $\delta $ clearly respects containment of spans) and that $j< u_j$ (otherwise, consider instead $w^{-1}$ , which avoids 3412, and $u^{-1}$ ). By assumption, $k, u_k \in [j, u_j]$ , so $\alpha _i(k)$ and $\alpha _{w_i}(u_k)$ are in $[j, u_j+1]$ . We have

$$ \begin{align*}\sigma(\alpha_i(j), \alpha_{w_i}(u_j))= \left\{\begin{array}{@{}llr} [j, u_j] & \text{ if }j < i, u_j < w_i, &\quad\quad \text{(Case I')}\cr [j, u_j+1] & \text{ if }j < i, u_j \geq w_i, & \quad\quad\text{(Case II')}\cr [j+1, u_j] & \text{ if }j \geq i, u_j < w_i, & \quad\quad\text{(Case III')}\cr [j+1, u_j+1] & \text{ if }j \geq i, u_j \geq w_i. & \quad\quad\text{(Case IV')} \end{array}\right. \end{align*} $$

Case I’: The only way $\sigma (\alpha (k, u_k))$ could fail to be contained in $\sigma (\alpha (j, u_j))$ is if $u_j+1 \in \{\alpha _i(k), \alpha _{w_i}(u_k)\}$ . Suppose that this occurs. Because $u_k< u_j$ , we must have $k=u_j$ and $k \geq i$ . In addition, $u_k< u_j< w_i$ . So, $\alpha (k, u_k)=(k+1, u_k)$ and $\alpha (j, u_j)=(j, u_j)$ . To summarize, we have $j< i< k+1$ and $w_{k+1}< w_j< w_i$ . So, $w_j w_i w_{k+1}$ form a 231 pattern.

Because $(k+1, w_k)$ and $(j, w_j)$ are corners and are not sandwiched by any inversions, w has no inversions of the form $\langle a, j \rangle $ or $\langle k+1, a \rangle $ . In addition, any a forming an inversion with i and $k+1$ but not j would give rise to a 3412 pattern, so no such a exist.

Consider $a>k+1$ . If $w_a < w_j$ , then a would either form an inversion with $k+1$ , which is impossible, or a would form an inversion with both i and j but not $k+1$ , which is also impossible. So, $w[k+2, n] \subseteq [w_j, n]$ . Because $j< k+2$ and $w_j=k$ , in fact, $w[k+2, n] \subseteq [k+1, n]$ . Notice that $w_i \geq k+1$ and $i < k+1$ , so we can refine this further to $w[k+2, n] = [k+1, n] \setminus \{w_i\}$ . But $(i, w_i)$ is sandwiched by some inversion $\langle a, b \rangle $ , so $a< i< k+1$ and $w_a>w_i \geq k+1$ . This is clearly a contradiction.

Case II’: By assumption, $\sigma (\alpha (k, u_k)) \subseteq [j, u_j+1]$ , so the claim is true.

Case III’: The only way $\sigma (\alpha (k, u_k))$ could fail to be contained in $\sigma (\alpha (j, u_j))$ is if j or $u_j+1$ were in $\{\alpha _i(k), \alpha _{w_i}(u_k)\}$ . Suppose that $j \in \{\alpha _i(k), \alpha _{w_i}(u_k)\}$ . Because $k>j$ , this means $u_k=j=\alpha _{w_i}(u_k)$ and $w_i>u_k$ . So, $\alpha (k, u_k)=(k+1, u_k)$ and we have $i< j+1< k+1$ and $w_{k+1}< w_{j+1}< w_i$ . This means that $(j+1, w_{j+1})$ is sandwiched by the inversion $\langle i, k+1 \rangle $ , a contradiction. The other case is similar.

Case IV’: The only way $\sigma (\alpha (k, u_k))$ could fail to be contained in $\sigma (\alpha (j, u_j))$ is if $j \in \{\alpha _i(k), \alpha _{w_i}(u_k)\}$ . This is similar to Case I’, so we leave it to the reader.

For (2): The map

$$ \begin{align*} \beta: \{B_{j, w_j}: (j, w_j) \in \overline{S}_w\} &\to \{B_{k, u_k}: k=1, \dots, n\}\\ B_{j, w_j} & \mapsto B_{\delta_i(j),\delta_{w_i}(w_j)} \end{align*} $$

is well defined and injective, because $\alpha $ and $\delta $ preserve span containment (for corners) and thus also preserve equality of spans (for corners). So, $B_{\delta _i(j),\delta _{w_i}(w_j)}=B_{\delta _i(k),\delta _{w_i}(w_k)}$ if and only if $B_{j, w_j}=B_{k, w_k}$ . Its image is the bounding boxes of $\Gamma [e, u]$ , because $\delta $ is a bijection between spanning corners of $\Gamma [e, w]$ and spanning corners of $\Gamma [e, u]$ .

We will show $\beta $ preserves the colors of the boxes by contradiction. Suppose the color of $\beta (B_{j, w_j})$ differs from the color of $B_{j, w_j}$ . This situation means that the relative order of $j, w_j$ must be different from that of $\delta _i(j), \delta _{w_i}(w_j)$ . This can only happen if $\min (j, w_j)$ is not shifted down by $\delta _a$ (for the appropriate $a \in \{i, w_i\}$ ), $\max (j, w_j)$ is shifted down by $\delta _b$ (for $b \in \{i, w_i\} \setminus \{a\}$ ) and $|j-w_j|\leq 1$ . That is, $\min (j, w_j)< a$ and $\max (j, w_j)>b$ . If $j=w_j$ , this implies $(j, w_j)$ is spanned by $(i, w_i)$ , a contradiction. Otherwise, this implies $(i, w_i)$ is spanned by $(j, w_j)$ . Because $|j-w_j|=1$ , the only possibility for this is that $i=w_j$ and $w_i=j$ , so the spans are equal. But $(j, w_j)$ is a corner and $(i, w_i)$ is not, a contradiction.

This means $\beta $ sends green bounding boxes to green bounding boxes, blue to blue, and red to red. It also sends purple to purple: suppose $(j, w_j)$ is a spanning corner and $B_{j, w_j}$ is purple. Then, $(w_j, j)$ is also a spanning corner of $\Gamma [e, w]$ and is not equal to $(j, w_j)$ . Because the span of $(j, w_j)$ and $(w_j, j)$ are the same, the span of $\delta (j, w_j)$ and $\delta (w_j, j)$ are the same; because $\delta $ is a bijection on spanning corners, $\delta (j, w_j) \neq \delta (w_j, j)$ . So, $B_{\delta (j, w_j)}=B_{\delta (w_j, j)}$ , and this bounding box is both red and blue.

For (3): Suppose $B_{j, w_j}$ and $B_{k, w_k}$ are two bounding boxes of $\Gamma [e, w]$ and $B_{j, w_j}$ precedes $B_{k, w_k}$ in the order given. That is, $\min (j, w_j)<\min (k, w_k)$ . Suppose for the sake of contradiction that $\min (\delta _i(j), \delta _{w_i}(j)) \geq \min (\delta _i(k), \delta _{w_i}(k))$ . In fact, because $\delta _a$ shifts numbers by at most 1, the only possibility is that $\min (\delta _i(j), \delta _{w_i}(j)) = \min (\delta _i(k), \delta _{w_i}(k))$ . Because $\delta (j, w_j)$ and $\delta (k, w_k)$ are both spanning corners of $\Gamma [e, u]$ and thus have maximal span, this implies that the span of $\delta (j, w_j)$ is equal to the span of $\delta (k, w_k)$ . So, $B_{\delta (j, w_j)}=B_{\delta (k, w_k)}$ . Because $\beta $ is a bijection, this implies $B_{j, w_j}=B_{k, w_k}$ , a contradiction.▪

Proof of Lemma 8.2 We may assume $i< w_i$ , so $B_{i, w_i}$ is blue; otherwise, we can consider $w^{-1}$ , which will still avoid $3412$ , $u^{-1}$ , which can be obtained from $w^{-1}$ by the same procedure as u is obtained from w, and the bounding box $B_{w_i, i}$ , which is blue. The intersection $\Gamma [e, w^{-1}] \cap B_{w_i, i}$ is simply the transpose of $B_{i, w_i} \cap \Gamma [e, w]$ .