# Subwords and Plane Partitions

Zachary Hamaker† and Nathan Williams‡

IMA, University of Minnesota 306 Lind Hall Minneapolis, MN U.S.A. 55455

LaCIM, Université du Québec à Montréal, C.P. 8888, Succ. Centre-Ville, Montréal, Québec, H3C 3P8, Canada

**Abstract.** Using the powerful machinery available for reduced words of type $B$, we demonstrate a bijection between centrally symmetric $k$-triangulations of a $2(n + k)$-gon and plane partitions of height at most $k$ in a square of size $n$. This bijection can be viewed as the type $B$ analogue of a bijection for $k$-triangulations due to L. Serrano and C. Stump.

**Résumé.** En utilisant la machinerie puissante pour mots réduits de type $B$, nous démontrons une bijection entre les $k$-triangulations centralement symétriques d'un $2(n + k)$-gon et les partitions de plans d'hauteur inférieure ou égale à $k$ dans un carré de taille $n$. Cette bijection peut être considérée comme l'analogue de type $B$ d'une bijection de $k$-triangulations due à L. Serrano et C. Stump.

**Keywords:** centrally symmetric $k$-triangulation, subword complex, plane partition, reduced word, linear extension, insertion, Little bump

## 1 Introduction

A *k*-triangulation of a regular convex $n$-gon is a maximal set of edges of the $n$-gon such that no $k+1$ of them mutually cross. J. Jonsson showed non-bijectively that the number of $k$-triangulations of an $(n+2k+1)$-gon was equal to the number of plane partitions of height at most $k$ in a staircase in [12]. L. Serrano and C. Stump proved this result bijectively in [26], synthesizing work in [4, 8, 21, 34].

**Theorem 1 ([26])** There is an explicit bijection between $k$-triangulations of an $(n+2k+1)$-gon and plane partitions of height at most $k$ in a staircase of size $n$.

D. Soll and V. Welker introduced *centrally symmetric $k$-triangulations* of a $2n$-gon as a type $B$ analogue of $k$-triangulations [27]. They conjectured that the number of centrally symmetric $k$-triangulations of a $2(n+k)$-gon was equal to the number of plane partitions in an $n \times n \times k$ box (and proved it as a lower bound). Their formula was subsequently proven non-bijectively by M. Rubey and C. Stump [25]. The main result of this abstract may be interpreted as a bijective proof of this fact.

**Theorem 2** There is an explicit bijection between centrally symmetric $k$-triangulations of a $2(n+k)$-gon and plane partitions of height at most $k$ in a square of size $n$.
<figure><img src="image_1.png" /><figcaption>**Fig. 1:** An example of the bijection in Theorem 2 for $n = 3$ and $k = 2$. On the left is a 2-triangulation of a 10-gon; on the right is the corresponding plane partition of height 2 in a square of size 3.</figcaption></figure>

Examples of Theorems 1 and 2 are given in Figures 2, 3, and 4.

To explain our approach to the bijection, we provide some additional context. V. Pilaud and M. Pocchiola introduced a duality between the *k-stars* in a *k*-triangulation and pseudolines, and showed that *k*-triangulations may be interpreted as certain pseudoline arrangements [21]. C. Stump rephrased this bijection in Coxeter-theoretic language [30], and a generalization of *k*-triangulations to all finite Coxeter groups was subsequently defined by C. Ceballos, J.-P. Labbé, and C. Stump [6]. Their construction recovers *k*-triangulations in type $A_n$ and centrally symmetric *k*-triangulations in type $B_n$.

Following [6], define $S_c(W, k)$ to be the set of *subwords* for $w_◦$ in the (non-reduced) word $c^k w_◦(c)$, where $c$ is a Coxeter element and $w_◦(c)$ is the *c-sorting word* for $w_◦$ (see the discussion before Definition 7). In crystallographic type, let $\mathcal{J}(W, k) := \mathcal{J}(\Phi^+(W) \times [k])$ be the set of *plane partitions* of height $k$ in the positive root poset $\Phi^+(W)$ (see Definition 15). In types $H_3$ and $I_2(m)$, we use D. Armstrong's surrogate "root posets" [1].

**Theorem 3 ([6, 32])** For $W = A_n, B_n, H_3$, or $I_2(m)$ and $k > 0$, $|S_c(W, k)| = |\mathcal{J}(W, k)|$.

For $W$ a finite Coxeter group, let $\mathcal{R}(W)$ be the set of *reduced words* for the longest element $w_◦$, and if $W$ is additionally a Weyl group then let $\mathcal{L}(W)$ be the set of *linear extensions* of the positive root poset $\Phi^+(W)$. P. Edelman and C. Greene found a bijection between $\mathcal{R}(W)$ and $\mathcal{L}(W)$ in type $A_n$, and M. Haiman proved the corresponding result in type $B_n$ (confirming a conjecture of R. Proctor) [7, 10]. In the noncrystallographic types $H_3$ and $I_2(m)$, it was observed in [32] that linear extensions of D. Armstrong's "root posets" also satisfy a similar bijection with $\mathcal{R}(W)$.

**Theorem 4 ([7, 10, 28, 32])** For $W = A_n, B_n, H_3$, or $I_2(m)$, there is a bijection between $\mathcal{R}(W)$ and $\mathcal{L}(W)$.

Ignoring redundancies like $D_3 \cong A_3$, neither Theorem 4 nor Theorem 3 holds in other finite types (for this reason the types $A_n, B_n, H_3$, and $I_2(m)$ are called "coincidental" in [32]). Since $A_n, B_n, H_3$, and $I_2(m)$ each have a linear Coxeter diagram, we may permanently fix $c$ to be a product of simple reflections from left to right in the diagram and write $S(W, k) := S_c(W, k)$.

In this language, we now explain the bijection of Theorem 1 to motivate our bijection in Theorem 2. In type $A_n$ and for $k = 1$, A. Woo used an observation of [4] to induce P. Edelman and C. Greene's

<footnote>†Email: zachary.hamaker@gmail.com. Z.H. is supported by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.</footnote>

<footnote>‡Email: nathan.f.williams@gmail.com. N.W. is supported by a postdoctoral position at LaCIM.</footnote>
bijective proof of Theorem 4 into a bijective proof of Theorem 3 [34]. L. Serrano and C. Stump subsequently extended A. Woo's construction to all $k$, explicitly connecting V. Pilaud and M. Pocchiola's pseudoline arrangements with E. Miller and A. Knutson's subword complex [13, 26]. This theorem may be summarized as saying that in type $A_n$, there is a “combinatorial lift” of Theorem 4 to Theorem 3:

$$ S(A_n, k) \xrightarrow{\text{Theorem 3}} \mathcal{R}(A_n) \xrightarrow{\text{Theorem 4}} \mathcal{L}(A_n) \xrightarrow{\text{Theorem 5}} \mathcal{J}(A_n, k). \quad (1) $$

Surprisingly, the analogous procedure in the remaining types—types $B_n$, $H_3$, and $I_{2m}$—does not quite work. In this paper, we propose a similar result in type $B_n$, proving a conjecture from [32]. Our bijection is most easily explained using the cube of Figure 2, which displays the relationships between reduced words $\mathcal{R}$, linear extensions $\mathcal{L}$, subwords $S$, and plane partitions $\mathcal{J}$ of both type $B_n$ and for the parabolic quotient $A_{2n-1}^n := A_{2n-1}^{\{s_n\}}$ (see Definition 11 for the definitions of $\mathcal{R}$, $\mathcal{L}$, $S$, and $\mathcal{J}$ for $A_{2n-1}^n$).

<figure><img src="image_2.png" /><figcaption>Fig. 2: The bijections between $\mathcal{R}$, $\mathcal{L}$, $S$, and $\mathcal{J}$ for $B_n$ and $A_{2n-1}^n$.</figcaption></figure>

In this cube, two vertices are connected by a solid line iff they are equinumerous. The dotted lines represent where a “combinatorial lift” may take place—for example, linear extensions are maximal chains of order ideals and reduced words are maximal chains in the weak order. Note that one can draw similar cubes in types $A_n$, $H_3$, and $I_2(m)$ [32].

Our bijection between centrally symmetric $k$-triangulations and plane partitions may be interpreted as

$$ \mathfrak{R}: \quad S(B_n, k) \dashrightarrow \mathcal{R}(B_n) \dashrightarrow \mathcal{L}(B_n) \dashrightarrow \mathcal{L}(A_{2n-1}^n) \dashrightarrow \mathcal{J}(A_{2n-1}^n, k), \quad (2) $$

which—as with L. Serrano and C. Stump's type $A_n$ result [26]—is again a “combinatorial lift” of Theorem 4, but now combined with a necessary extra step to the parabolic quotient. Figure 2 suggests the second, more direct, path

$$ \mathcal{L}: \quad S(B_n, k) \dashrightarrow \mathcal{L}(B_n) \dashrightarrow \mathcal{L}(A_{2n-1}^n, k) \dashrightarrow \mathcal{J}(A_{2n-1}^n, k), \quad (3) $$

which is based on the type $B_n$. Little map. We prove Theorem 2 by showing that $\mathcal{L}\mathcal{C}$ is a bijection and also show that $\mathcal{L}\mathcal{C} = \mathfrak{R}\mathfrak{R}$.
It is clear that Theorem 1 is a bijective version of Theorem 3 in type $A_n$, but this is not immediately the case for Theorem 2. Indeed, although R. Proctor proved that $|\mathcal{J}(B_n, k)| = |\mathcal{J}(A_{2n-1}^n, k)|$ by interpreting each side as a representation of Lie algebras and then equating them with a branching rule [23], we do not know of a bijection between plane partitions of height $k$ in a trapezoid and in a square. Without such a correspondence, Theorem 2 fails to provide a bijection between $S(B_n, k)$ and $\mathcal{J}(B_n, k)$.

The remainder of this abstract is structured as follows. In Section 2, we recall the correspondence between $k$-triangulations and centrally symmetric $k$-triangulations and certain subwords of types $A$ and $B$. In Section 3, we give the bijections for fully commutative elements, explaining the outer square of Figure 2. In Section 4, we relate reduced words and linear extensions of types $A_{2n-1}^n$ and $B_n$, explaining the top square of Figure 2. In Section 5, we recall Theorem 1 in greater detail. In Section 6, we state and prove our bijection between centrally symmetric $k$-triangulations and plane partitions in a box, establishing Theorem 2. Finally, in Section 7, we discuss generalizations and future directions of research.

## 2 $k$-Triangulations and Subwords

In this section, we introduce $k$-triangulations and we recall the bijection between $k$-triangulations of an $(n+2k+1)$-gon and $S(A_n, k)$ and centrally symmetric $k$-triangulations of an $2(n+k)$-gon and $S(B_n, k)$.

**Definition 5** A $k$-triangulation $T$ of a regular convex $n$-gon is a maximal set of diagonals of the $n$-gon such that no $k+1$ of them are mutually crossing. We write $\text{Tri}_A(n, k)$ for the set of all such $T$. A centrally symmetric $k$-triangulation $T$ of a $2n$-gon is $k$-triangulation that is invariant under rotation of the $2n$-gon by $\pi$ radians. We write $\text{Tri}_B(2n, k)$ for the set of all such $T$.

The simplicial complex generated by all subsets of elements of $\text{Tri}_A(n, k)$ generalizes the type $A_n$ associahedron, which is obtained for $\text{Tri}_A(n+3, 1)$. In [12], J. Jonsson enumerated $\text{Tri}_A(n, k)$. The centrally symmetric $k$-triangulations were introduced to generalize R. Simion's type $B_n$ associahedron; $|\text{Tri}_B(2n, k)|$ was conjectured in [27] and proven non-bijectively in [25].

**Theorem 6** ([12, 25]) The number of $k$-triangulations and centrally symmetric $k$-triangulations are given by

$$|\text{Tri}_A(n+2k+1, k)| = \prod_{1 \le i \le j \le n} \frac{i+j+2k}{i+j} \quad \text{and} \quad |\text{Tri}_B(2(n+k), k)| = \prod_{h=1}^{k} \prod_{i=1}^{n} \prod_{j=1}^{n} \frac{h+i+j-1}{h+i+j-2}.$$

Our main theorem, Theorem 2, is therefore a bijective proof of this enumeration for $\text{Tri}_B(2(n+k), k)$.

An edge is called *k-relevant* if it has at least $k$ vertices on either side (not including its end points). The *k-relevant* edges are exactly those that could be involved in a (*k*+1)-crossing, so that every *k*-triangulation contains all non-*k*-relevant edges. A *k-star* is a set of edges of the form $\{v_j v_{j+k} : j \in \mathbb{Z}_{2k+1}\}$, for some set of vertices $v_0, v_1, \dots, v_{2k}$ that are in order clockwise about the *n*-gon. By extending properties of triangles to *k*-stars, V. Pilaud and P. Santos defined an analogue of the Tamari lattice on *k*-triangulations [22]. Drawing on the structure given by the *k*-stars and a duality—which we do not explain here, although see the remark after Theorem 8—between *k*-stars and pseudolines, V. Pilaud and M. Pocchiola discovered an elegant bijection between multitriangulations and certain pseudoline arrangements [21]. It is most efficient for our purposes to describe these pseudoline arrangements using a restatement of this bijection due to C. Stump in type $A_n$ and due to C. Ceballos, J. P. Labbé, and C. Stump for all finite Coxeter groups [6, 30].
Let $(W, S)$ be a finite Coxeter system. A *Coxeter element* $c = s_{\pi_1}s_{\pi_2}\cdots s_{\pi_n}$ is a product of the simple reflections $S$ in any order. Since we will only consider types $A_n, B_n, H_3$, and $I_2(m)$, we now *permanently* fix a reduced word $c$—and hence a Coxeter element $c$—in each type to be the product from left to right of the following labelings of the Coxeter diagrams by simple reflections:

$$ \begin{array}{ccccccc} & A_n & & B_n & & H_3 & I_2(m) \\ s_1 & - & s_2 & - & \cdots & - & s_{n-1} & - \\ & & s_0 & - & \cdots & - & s_{n-2} & - \\ & & & & \ddots & & s_{n-1} & - \\ & & & & & s_1 & - & \cdots \\ & & & & & & s_2 & - \\ & & & & & & & s_1 & - \\ & & & & & & & & s_2 \end{array} $$

For $w \in W$, a *subword* for $w$ in a (possibly infinite) word $\mathbf{a} = a_1a_2a_3\cdots$ with $a_i \in S$ is a reduced word $a_{i_1}a_{i_2}\cdots a_{i_\ell}$ for $w$ such that $i_1 < i_2 < \cdots i_\ell$. The *c-sorting word* $\mathbf{w}(\mathbf{c})$ of $w$ is the lexicographically first (in position) reduced subword for $w$ of the word $c^\infty$ [24].

**Definition 7** Given $w \in W$ and a possibly non-reduced word $\mathbf{a} = a_1 \cdots a_r$ with $a_i \in S$, let $S(\mathbf{a}, w)$ be the set of subwords for $w$ in $\mathbf{a}$. Define $S(W, k) := S(c^k \mathbf{w}_\circ(\mathbf{c}), w_\circ)$.

**Theorem 8** [6,21] There are bijections between $S(A_n, k)$ and $\text{Tri}_A(n+2k+1, k)$, and between $S(B_n, k)$ and $\text{Tri}_B(2(n+k), k)$.

In type $A_n$, the bijection of Theorem 8 associates $k$-relevant edges with letters of $c^k \mathbf{w}_\circ(\mathbf{c})$. In type $B_n$, the bijection associates $k$-relevant symmetric pairs of edges with letters. For example, see Figures 3 and 4. For more details, see the excellent examples in [6].

## 3 Correspondences for Fully Commutative Elements

This section briefly describes the square of Figure 2 containing the objects $\mathcal{R}(A_{2n-1}^n), \mathcal{L}(A_{2n-1}^n)$, $S(A_{2n-1}^n, k)$, and $\mathcal{J}(A_{2n-1}^n, k)$.

Let $(W, S)$ be a finite Coxeter system and for $w \in W$ let $\mathcal{R}(w)$ be the set of reduced words in the simple generators $S$ for $w$. Any two reduced words $\mathbf{w}, \mathbf{w}' \in \mathcal{R}(w)$ may be transformed to each other using only braid moves—that is, the graph on $\mathcal{R}(w)$ with edges given by braid moves is connected. We say that $\mathbf{w}$ and $\mathbf{w}'$ lie in the same *commutation class* if one may be transformed into the other using only commutations.

**Definition 9** An element $w \in W$ is *fully commutative* iff all reduced words for $w$ lie in the same commutation class.

For $w$ fully commutative, the interval in the weak order $[e, w]$ is a distributive lattice (and coincides with corresponding interval in the Bruhat order) [29]. To see this, we construct its poset of join-irreducibles.

Fix $w \in W$ and let $\mathbf{w} = w_1 \cdots w_\ell$ be a reduced word for $w$, so that $w_i \in S$ and $\ell = \ell(w)$ is the length of $w$. Define a partial order $\prec_w$ on $[\ell]$ by the transitive closure of the relations $i \prec_w j$ if $i < j$ and $w_i w_j \neq w_j w_i$. This partial ordering defines a “root poset” $\Phi^+(\mathbf{w})$ on $[\ell]$ called a *heap* [29, 31]. We may label the elements of $\Phi^+(\mathbf{w})$ by replacing $i$ by $a_i$. If $\mathbf{w}, \mathbf{w}'$ are any two reduced words for a fully commutative element $w$, then it is not difficult to see that $\Phi^+(\mathbf{w})$ and $\Phi^+(\mathbf{w}')$ are isomorphic. We may therefore refer to the heap $\Phi^+(w)$ of a fully commutative $w \in W$.

Recall that a *linear extension* of a finite poset $\mathcal{P}$ with $\ell$ elements is a bijection $\mathcal{L}: \mathcal{P} \to [\ell]$ such that if $p \prec_{\mathcal{P}} p' \in \mathcal{P}$, then $\mathcal{L}(p) < \mathcal{L}(p')$. The weak order interval $[e, w]$ is now described by $\Phi^+(w)$.
**Theorem 10** ([29]) For $w$ fully commutative, there is a bijection between $\mathcal{L}(\Phi^+(w))$ and $\mathcal{R}(w)$. This induces a bijection between $\mathcal{J}(\Phi^+(w))$ and the elements in the interval $[e, w]$.

**Proof:** The first statement is clear from the definitions: a linear extension $\mathcal{L}: \Phi^+(w) \to [\ell]$ corresponds to the reduced word $\prod_{i=1}^{\ell} w_{\mathcal{L}^{-1}(i)}$. For the second statement, fix an order ideal $I$ of $\Phi^+(w)$, choose any linear extension $\mathcal{L}$ of $\Phi^+(w)$ with initial part in $I$—that is, such that $\mathcal{L}(j) \le |I|$ for $j \in I$. The element in $[e, w]$ corresponding to $I$ is then $\prod_{i=1}^{|I|} w_{\mathcal{L}^{-1}(i)}$. $\square$

We remark that Theorem 10 already gives us the flavor of a “combinatorial lift,” since it uses the correspondence between $\mathcal{L}(\Phi^+(w))$ and $\mathcal{R}(w)$ to induce a bijection between $\mathcal{J}(\Phi^+(w))$ and $[e, w]$.

Let $J \subseteq S$ be a subset of the simple generators and let $W_J$ be the corresponding *parabolic subgroup* of $W$ generated by $J$. The *parabolic quotient* $W^J$ is the set of minimal coset representatives for $W/W_J$ [5]. For finite $W$, the parabolic quotient $W^J$ has a longest element $w_0^J$ and $W^J$ is the interval $[e, w_0^J]$.

**Definition 11** Let $w_0^{\{s_n\}}$ be the longest element of $A_{2n-1}^n := A_{2n-1}^{\{s_n\}}$. We write $\mathcal{R}(A_{2n-1}^n) := \mathcal{R}(w_0^{\{s_n\}})$, $\mathcal{L}(A_{2n-1}^n) := \mathcal{L}(\Phi^+(w_0^{\{s_n\}}))$, $\mathcal{S}(A_{2n-1}^n, k) := \mathcal{S}(c^{k+n}, w_0^{\{s_n\}})$, $\mathcal{J}(A_{2n-1}^n, k) := \mathcal{J}(\Phi^+(w_0^{\{s_n\}}) \times [k])$.

It is easy to check that $\Phi^+(w_0^{\{s_n\}})$ is an $n \times n$ square—the inversions of $w_0^{\{s_n\}}$ are the order filter in the root poset $\Phi^+(A_{2n-1})$ generated by the simple root $\alpha_n$. Since the element $w_0^{\{s_n\}}$ is fully commutative, Theorem 10 implies the following corollary [29].

**Corollary 12** There is a bijection $\mathcal{C}_{\mathcal{R}}^{\mathcal{L}}$ between $\mathcal{R}(A_{2n-1}^n)$ and $\mathcal{L}(A_{2n-1}^n)$.

We now explain the map between $\mathcal{S}(A_{2n-1}^n, k)$ and $\mathcal{J}(A_{2n-1}^n, k)$. Let $w \in W$ be a fully commutative element, and fix a reduced word $\mathbf{w} = w_1w_2 \cdots w_\ell$ with $w_i \in S$. For such a $\mathbf{w}$, let $t_{\mathbf{w},i} = w_1 \cdots w_{i-1}w_iw_{i-1} \cdots w_1$. Let $\mathbf{a} = a_1a_2 \cdots a_r$ with $a_i \in S$ be a (possibly non-reduced) word in the simple reflections. For each letter $w_i$ of $\mathbf{w}$, let

$$ \mathbf{a}(i) := \{j : j = i_t \text{ for some } 1 \le t \le \ell \text{ in some } \mathbf{w}' = a_{i_1} \cdots a_{i_\ell} \in \mathcal{S}(\mathbf{a}, w) \text{ such that } t_{\mathbf{w},i} = t_{\mathbf{w}',j}\} $$

be the set of letters of $\mathbf{a}$ corresponding to the letter $w_i$ of $\mathbf{w}$ in some subword of $\mathcal{S}(\mathbf{a}, w)$. Since $w$ is fully commutative, the set $\{\mathbf{a}(i) : 1 \le i \le \ell\}$ does not depend on the initial choice $\mathbf{w}$. Define the set of triples

$$ \Phi^+(\mathbf{a}, w) := \{(i, a, b) : 1 \le i \le \ell, a < b \in \mathbf{a}(i) \text{ with no } c \in \mathbf{a}(i) \text{ for which } a < c < b\}. $$

We now endow $\Phi^+(\mathbf{a}, w)$ with a partial order given by the transitive closure of the relations $(i, a, b) \succ_a (i, b, c)$ and $(j, c, d) \succ_a (i, a, b)$ if $i < j$, $w_i$ and $w_j$ don't commute, and $a < c$. We call this partial ordering the *subword heap* for $w$ with respect to $\mathbf{a}$, and denote it by $\Phi^+(\mathbf{a}, w)$ [32].

**Theorem 13** ([32]) For $w \in W$ fully commutative, there is a bijection between $\mathcal{J}(\Phi^+(\mathbf{a}, w))$ and $\mathcal{S}(\mathbf{a}, w)$.

**Proof:** An order ideal $I \in \mathcal{J}(\Phi^+(\mathbf{a}, w))$ corresponds to the subword $a_{i_1} \cdots a_{i_\ell}$ of $\mathcal{S}(\mathbf{a}, w)$, where for $1 \le j \le \ell$, we set $i_j := \min(\{a : (j, a, b) \in I\} \cup \{\max\{b : (j, a, b) \in \Phi^+(\mathbf{a}, w)\}\})$. $\square$

Since $c = s_1s_2 \cdots s_{2n-1}$, $w_0^{\{s_n\}}$ is fully commutative, and $w_0^{\{s_n\}}$ has the explicit reduced word $(s_n \cdots s_{2n-1})(s_{n-1} \cdots s_{2n-2}) \cdots (s_1 \cdots s_n)$, Theorem 13 implies the following corollary.

**Corollary 14** There is a bijection $\mathcal{C}_{\mathcal{S}}^{\mathcal{J}}$ between $\mathcal{S}(A_{2n-1}^n, k)$ and $\mathcal{J}(A_{2n-1}^n, k)$.
# 4 Reduced Words, Linear Extensions, and Little Bumps

This section describes the square of Figure 2 containing $\mathcal{R}(B_n)$, $\mathcal{L}(B_n)$, $\mathcal{R}(A_{2n-1}^n)$, and $\mathcal{L}(A_{2n-1}^n)$.

## 4.1 Reduced Words and Linear Extensions

This section provides more detail on the highly nontrivial Theorem 4. In particular, we describe the bijections between $\mathcal{R}(B_n)$ and $\mathcal{L}(B_n)$ and between $\mathcal{R}(A_n)$ and $\mathcal{L}(A_n)$.

When $w$ is not fully commutative, $\mathcal{R}(w)$ becomes a connected graph only when we are allowed both commutations *and* the longer braid moves of $W$ (see Theorem 3.3.1 in [5]). The theory of the previous section therefore cannot be applied to general reduced words. Remarkably, there is a poset that often behaves like a heap for the longest element $w_◦$ of $W$. Recall that a general Coxeter group has a correspondence between its *reflections* $T := \{wsw^{-1} : s \in S\}$ and its *positive roots* [5].

**Definition 15** The root poset $\Phi^+(W)$ is the partial order on the positive roots of $W$ defined by $\alpha < \beta$ iff $\alpha - \beta$ is a nonnegative linear combination of positive roots.

This relationship between the root poset and the longest element is examined in more detail in [32, 33], where it is related to Catalan combinatorics (we note that Conjecture 4.4 of [33] is still open).

**Theorem 4** ([7, 10, 14, 32]) When $W$ is of type $A_n, B_n, H_3$, or $I_2(m)$, there is a bijection between $\mathcal{L}(W)$ and $\mathcal{R}(W)$. Under this bijection, the initial segments $\mathcal{L}^{-1}(\{1, 2, \dots, i\})$ of a linear extension $\mathcal{L}$ and $w_◦ = a_1a_2\cdots a_i$ of a reduced word $w_◦$ determine each other (this may be interpreted as the existence of explicit insertion procedures that take reduced words to linear extensions).

Note that Theorem 4 does not continue to hold in other types—for example, $|\mathcal{L}(D_4)| = 2400$, but $|\mathcal{R}(D_4)| = 2316$. *Kraśkiewicz insertion* is the insertion procedure $\Re : \mathcal{R}(B_n) \to \mathcal{L}(B_n)$, due to W. Kraśkiewicz [14, 16].

In [10], M. Haiman introduced a bijection called *rectification* between $\mathcal{L}(A_{2n-1}^n)$ and $\mathcal{L}(B_n)$. Given a square tableau, which we prefer to think of as an element of $\mathcal{L}(A_{2n-1}^n)$, one performs jeu-de-taquin slides until arriving at a tableau of trapezoidal shape, which we see as an element of $\mathcal{L}(B_n)$.

**Theorem 16** ([9]) There is a promotion-equivariant bijection $\Re_\mathcal{L} : \mathcal{L}(A_{2n-1}^n) \to \mathcal{L}(B_n)$.

## 4.2 Little Bumps

D. Little introduced *Little bumps* in [19]. These are a bijective realization of algebraic identities on Stanley symmetric functions derived from Monk's rule for Schubert polynomials, particularly the transition equations introduced by A. Lascoux and M.-P. Schützenberger [17]. Little bumps act at the level of reduced words by successively incrementing or decrementing the simple reflections in the word until a new reduced word (of the same length) is obtained. T. Lam conjectured that two reduced words have the same Edelman-Greene recording tableau iff they differ by a sequence of Little bumps. Z. Hamaker and B. Young proved this conjecture in [11], and showed that Little bumps preserve the Q-tableau.

In [2], S. Billey demonstrated transition equations for type *C* Stanley symmetric functions. The type *B* Little bumps, introduced by S. Billey, Z. Hamaker, A. Roberts and B. Young in [3], are a bijective realization of these, and other, equations. As the following theorem shows, the type *B* Little bumps relate to Kraśkiewicz insertion in the same way that Little bumps relate to Edelman-Greene insertion.
**Theorem 17** ([3]) Type B Little bumps preserve the Kraśkiewicz recording tableau $Q'$, and two reduced words have the same Kraśkiewicz recording tableau iff they differ by a sequence of type B Little bumps.

We now recall type B Little bumps. Using the usual (signed) permutation realization of the Coxeter group $B_n$, reflections may be specified as pairs $(i, j)$ such that $i \in [-n] \cup [n]$, $j \in [n]$ and $|i| \le j$.

For $w \in B_n$ let $s_{b_1} \cdots s_{b_\ell} \in \mathcal{R}(w)$ with corresponding word $\mathbf{b} = b_1 \cdots b_\ell$ with $b_i \in \{0, 1, \dots, n-1\}$— we abuse notation by associating $\mathbf{b}$ with $s_{b_1} \cdots s_{b_\ell}$. Let $w^{(m)} = s_{b_1} \cdots s_{b_m}$ with $w^{(0)}$ the identity. The wiring diagram of $\mathbf{b}$ is the diagram on $\{0, 1, \dots, \ell\} \times \mathbb{Z} \setminus \{0\}$ where $(i, j)$ is labeled by $(w^{(i)})^{-1}(j)$ and entries with the same label are connected from left to right. The trajectory of $i$ in $\mathbf{b}$ is the sequence $\{(w^{(j)})^{-1}(i)\}_{j=0}^\ell$, and corresponds to the entries of the wiring diagram labeled $i$.

A type B Little bump $B_{(i,j)}^\delta$ on the reduced word $\mathbf{b}$ is specified by a covered reflection $t_{(i,j)}$ of $w$—an inversion of $w$ such that $\ell(w \cdot t_{(i,j)}) + 1 = \ell(w)$—and a direction $\delta \in \{\pm 1\}$. Given $(i, j)$, identify the index $p$ in which the inversion $(i, j)$ is introduced in $\mathbf{b}$. Set $\mathbf{a} = \mathcal{P}_{\delta'}(\mathbf{b}, p)$, where the push $\mathcal{P}_{\delta'}$ fixes $b_j$ for $j \ne p$ and adds $\delta'$ to $b_p$. Here $\delta' = \delta$ if $\{w^{(p-1)}(b_p), w^{(p-1)}(b_p + 1)\} \cap \{i, j\} \ne \emptyset$ and $\delta' = -\delta$ otherwise. This condition ensures that the intersection of the trajectories of $i$ and $j$ in the wiring diagram is moved in the direction $\delta$. Here, $\mathbf{a}$ may not be reduced, in which case there is a unique index $p' \ne p$ such that the word $s_{a_1} \cdots \widehat{s_{a_{p'}} \cdots s_{a_\ell}}$ is reduced (this follows from the assumption that $t_{(i,j)}$ was a covered reflection and Lemma 21 of [15]). Then $a_{p'}$ and $a_p$ interchange the same values—up to sign—and we set $a_{p'} := \mathcal{P}_{\delta'}(a, p')$, iterating until we obtain a word $\mathbf{a}$ that is reduced. This algorithm is guaranteed to finish in finite time by [3, Lemma 3.5], and we set $B_{(i,j)}^\delta(\mathbf{b}) = \mathbf{a}$.

As observed in Section 4.1, for $\mathbf{a} \in \mathcal{R}(A_{2n-1}^n)$, the mixed insertion recording tableau $\mathcal{L}_{\mathcal{R}}(\mathbf{a})$ is in $\mathcal{L}(B_n)$, and coincides with its Kraśkiewicz recording tableau. Similarly, for $\mathbf{b} \in \mathcal{R}(B_n)$, Theorem 4 implies that its Kraśkiewicz recording tableau also gives $Q'(\mathbf{b}) \in \mathcal{L}(B_n)$. Since these insertions are invertible, we obtain a bijection

$$ \mathcal{L}_{\mathcal{R}} : \mathcal{R}(A_{2n-1}^n) \to \mathcal{R}(B_n) \text{ by setting } \mathcal{L}_{\mathcal{R}}(\mathbf{a}) = \mathbf{b} \text{ when } Q'(\mathbf{a}) = Q'(\mathbf{b}). $$

Theorem 17 tells us that the two reduced words $\mathbf{a}$ and $\mathbf{b}$ must be connected by a sequence of Little bumps. We now use the type B Little bumps to explicitly construct the bijection $\mathcal{L}_{\mathcal{R}}^{-1} : \mathcal{R}(B_n) \to \mathcal{R}(A_{2n-1}^n)$.

**Proposition 18** Define the sequences $J_k := (-1, 1), (1, 2), \dots, (k-1, k)$ with $J_1 := (-1, 1)$, and let $J$ be the concatenation $J := J_n, J_{n-1}, \dots, J_1$.

$$ \text{Then for } \mathbf{b} \in \mathcal{R}(B_n), \quad \left( \prod_{(i,j) \in J} B_{(i,j)}^{+1} \right) \mathbf{b} = \mathbf{a}, \quad \text{where } \mathbf{a} \in \mathcal{R}(A_{2n-1}^n) \text{ and } \mathcal{L}_{\mathcal{R}}(\mathbf{a}) = \mathbf{b}. $$

Using techniques from [3], this proposition can be reduced to showing the map works as described for a single element of $\mathcal{R}(B_n)$, which can then be readily verified for the word $c^n$. For example,

$$ \mathcal{R}(B_2) \ni 0101 \xrightarrow{B_{(-1,1)}^{+1}} 1201 \xrightarrow{B_{(1,2)}^{+1}} 2301 \xrightarrow{B_{(-1,1)}^{+1}} 2312 \in \mathcal{R}(A_3^2). $$

This Little map characterization provides more precise control over the relationship between $\mathbf{a} \in \mathcal{R}(A_{2n-1}^n)$ and $\mathcal{L}_{\mathcal{R}}(\mathbf{a}) \in \mathcal{R}(B_n)$. Recall that the peak set of a word $\mathbf{a} = a_1 \cdots a_r$ is the set $\text{Peak}(\mathbf{a}) := \{i : a_{i-1} < a_i > a_{i+1}\}$, while its descent set is $\text{Des}(\mathbf{a}) := \{i : a_i > a_{i+1}\}$. T-K. Lam showed that while $\mathbf{a}$ and $Q'(\mathbf{a})$ have the same peak set, in general they need not have the same descent set [16].
graph structure of type $A_{k-1}$ [20]. For example, in type $A_n$ with fundamental weights $\lambda_1, \lambda_2, \dots, \lambda_n$, $S(c^{n+1}, w_\circ)$ has a structure isomorphic to the crystal $A_n(\lambda_1 + \lambda_2 + \dots + \lambda_n)$.

To connect these two stories, note that the subwords $S(c^k w_\circ(c), w_\circ)$ in type $A_n$ are naturally a subset of the subwords $S(c^{n+k}, w_\circ)$. The bijection that J. Morse and A. Schilling provide between $S(c^{n+k}, w_\circ)$ and semistandard Young tableaux specializes to the bijection of Theorem 1 when restricted to this subset.

This crystal interpretation gives a second way (different from the theory of brick polytopes) to provide geometric embeddings of certain subword complexes.

# 6 Subwords and Plane Partitions for Type $B_n$

Rather than proceed as in Theorem 1, we follow the more direct path of Equation 3 to prove Theorem 2.

**Theorem 2** There is an explicit bijection between $\text{Tri}_B(2(n+k), k)$ and $\mathcal{J}(A_{2n-1}^n, k)$.

To define the lifting of the map $\mathcal{L}_R : \mathcal{R}(A_{2n-1}^n) \to \mathcal{R}(B_n)$ to a map $\mathcal{L}_S : S(A_{2n-1}^n, k) \to S(B_n, k)$, we will find it helpful to refer to a subword of $S(A_{2n-1}^n, k) = S((s_1s_2 \cdots s_{2n-1})^{n+k}, w_\circ^{\{s_n\}})$ by

$$ \mathbf{a}^{\mathbf{i}} = a_1^{i_1} a_2^{i_2} \cdots a_n^{i_n^2}, $$

where $i_j \in [n+k]$ records from which copy of $(s_1s_2 \cdots s_{2n-1})$ the simple reflection $a_i \in \{s_1, s_2, \dots, s_{2n-1}\}$ was taken. We use the same notation for subwords of $S(B_n, k) = S((s_0s_1 \cdots s_{n-1})^{n+k}, w_\circ)$—a sub-word is written $\mathbf{b}^{\mathbf{i}} = b_1^{i_1} b_2^{i_2} \cdots b_n^{i_n^2}$, where $i_j \in [n+k]$ records from which copy of $(s_0s_1 \cdots s_{n-1})$ the simple reflection $b_i \in \{s_0, s_1, \dots, s_{n-1}\}$ was taken.

**Proposition 21** Then the map $\mathcal{L}_S : S(A_{2n-1}^n, k) \to S(B_n, k)$, defined by

$$ \mathcal{L}_S(a_1^{i_1} a_2^{i_2} \cdots a_n^{i_n^2}) = b_1^{i_1} b_2^{i_2} \cdots b_n^{i_n^2}, $$

where $\mathcal{L}_R(a_1a_2 \cdots a_n^2) = b_1b_2 \cdots b_n^2$, is a bijection.

**Proof:** This follows from Lemma 19—the descent sets of $a_1a_2 \cdots a_n^2$ and $b_1b_2 \cdots b_n^2$ agree, so that increasing sequences in one are taken to increasing sequences in the other. Since the number of copies of $c$ are the same in $S(A_{2n-1}^n, k)$ and $S(B_n, k)$, the map is well-defined. $\square$

The proof of Theorem 2 now follows from Corollary 14 and Proposition 21. We now phrase this bijection similarly to the bijection given in Section 5. Let $N := n^2 = \ell(w_\circ)$ and $\mathbf{a} = a_1a_2 \cdots a_{k \cdot n + N} := c^{k+n}$. First, $\text{Tri}_B(2(n+k), k)$ is encoded as $S(B_n, k)$ using Theorem 8. Next, using Theorem 4, we apply Kraskiewicz insertion $\mathfrak{R}$ to a subword $a_{i_1}a_{i_2} \cdots a_{i_N}$ of $S(B_n, k)$ to produce a linear extension in $\mathcal{L}(B_n)$. At this point, rather than modify the linear extension of $\mathcal{L}(B_n)$, we next apply rectification $\mathcal{R}_L$ to produce a linear extension in $\mathcal{L}(A_{2n-1}^n)$, and only then do we modify the linear extension of $\mathcal{L}(A_{2n-1}^n)$ by replacing the letter $j$ by $\text{des}_\mathbf{a}(i_j) + 1$. Thinking of $\Phi^+(A_{2n}^n)$ as a tableau of square shape, we subtract $r$ from the $r$th row to obtain a plane partition of height at most $k$ of square shape.

As in type $A_n$, the construction above may be summarized as the “combinatorial lift” of Theorem 4 to Theorem 3 given in Equation 2. We can prove that $\mathfrak{R}\mathfrak{R} = \mathcal{LC}$ using the maps discussed in Section 4.1.

**Remark 22** The verbatim analogue of the map in type $A_n$ given in Equation 1 does not work as before. Although we may lift a subword to a linear extension and then modify the linear extension of $\mathcal{L}(B_n)$ by replacing the letter $j$ by $\text{des}_\mathbf{a}(i_j) + 1$, we do not have a bijection from the resulting tableaux to $\mathcal{J}(B_n, k)$.
[4] S. Billey, W. Jockusch, and R. Stanley, Some combinatorial properties of Schubert polynomials, J. of Alg. Comb. **2** (1993), no. 4, 345–374.

[5] A. Björner and F. Brenti, Combinatorics of Coxeter groups, Vol. 231, Springer, 2005.

[6] C. Ceballos, J.-P. Labbé, and C. Stump, Subword complexes, cluster complexes, and generalized multi-associahedra, J. of Alg. Comb. (2011), 1–35.

[7] P. Edelman and C. Greene, Balanced tableaux, Advances in Math. **63** (1987), no. 1, 42–99.

[8] S. Fomin and A. Kirillov, Reduced words and plane partitions, J. of Alg. Combin. **6** (1997), no. 4, 311–319.

[9] M. Haiman, On mixed insertion, symmetry, and shifted Young tableaux, J. of Combin. Theory, Series A **50** (1989), no. 2, 196–225.

[10] M. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math. **99** (1992), no. 1, 79–113.

[11] Z. Hamaker and B. Young, Relating Edelman–Greene insertion to the Little map, J. of Alg. Combin. **40** (2014), no. 3, 693–710.

[12] J. Jonsson, Generalized triangulations and diagonal-free subsets of stack polyominoes, J. of Combin. Theory, Series A **112** (2005), no. 1, 117–142.

[13] A. Knutson and E. Miller, Subword complexes in Coxeter groups, Advances in Mathematics **184** (2004), no. 1, 161–176.

[14] W. Kraśkiewicz, Reduced decompositions in hyperoctahedral groups, Comptes rendus de l'Académie des sciences. Série 1, Mathématique **309** (1989), no. 16, 903–907.

[15] T. Lam and Mark S., A Little bijection for affine Stanley symmetric functions, Sém. Lotharingien de Comb. **54** (2006), B54Ai.

[16] T.-K. Lam, $B_n$ Stanley symmetric functions, Discrete Math. **157** (1996), no. 1, 241–270.

[17] A. Lascoux and M-P. Schützenberger, Schubert polynomials and the Littlewood-Richardson rule, Letters in Mathematical Physics **10** (1985), no. 2-3, 111–124.

[18] C. Lenart, A unified approach to combinatorial formulas for Schubert polynomials, J. of Alg. Combin. **20** (2004), no. 3, 263–299.

[19] D. Little, Combinatorial aspects of the Lascoux–Schützenberger tree, Advances in Math. **174** (2003), no. 2, 236–253.

[20] J. Morse and A. Schilling, Crystal operators and flag Gromov-Witten invariants, preprint (2014).

[21] V. Pilaud and M. Pocchiola, Multitriangulations, pseudotriangulations and primitive sorting networks, Discrete & Computational Geometry **48** (2012), no. 1, 142–191.

[22] V. Pilaud and F. Santos, Multitriangulations as complexes of star polygons, Discrete & Computational Geometry **41** (2009), no. 2, 284–317.

[23] R. Proctor, Shifted plane partitions of trapezoidal shape, Proc. of the American Math. Society **89** (1983), no. 3, 553–559.

[24] N. Reading, Sortable elements and Cambrian lattices, Algebra Universalis **56** (2007), no. 3-4, 411–437.

[25] M. Rubey and C. Stump, Crossings and nestings in set partitions of classical types, Electron. J. Combin **17** (2010).

[26] L. Serrano and C. Stump, Generalized triangulations, pipe dreams, and simplicial spheres, Electron. J. Combin. **19** (2012).

[27] D. Soll and V. Welker, Type-B generalized triangulations and determinantal ideals, Dis. Math. **309** (2009), no. 9, 2782–2797.

[28] R. Stanley, On the number of reduced decompositions of elements of Coxeter groups, European J. Combin **5** (1984), no. 4, 359–372.

[29] J. Stembridge, On the fully commutative elements of Coxeter groups, J. of Alg. Combin. **5** (1996), no. 4, 353–385.

[30] C. Stump, A new perspective on k-triangulations, J. of Combin. Theory, Series A **118** (2011), no. 6, 1794–1800.

[31] G. Viennot, Heaps of pieces, I: Basic definitions and combinatorial lemmas, Combinatoire énumérative, 1986, pp. 321–350.

[32] N. Williams, Cataland, Dissertation, University of Minnesota, 2013.

[33] N. Williams, Bijactions in Cataland, DMTCS Proceedings **01** (2014), 597–608.

[34] A. Woo, Catalan numbers and Schubert polynomials for $w = 1(n+1)\dots2$, arXiv preprint math (2004).