Zachary Hamaker
email: zachary.hamaker@gmail.com.

Nathan Williams
email: nathan.f.williams@gmail.com.

Subwords and Plane Partitions

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

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

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 [START_REF] Jonsson | Generalized triangulations and diagonal-free subsets of stack polyominoes[END_REF]. L. Serrano and C. Stump proved this result bijectively in [START_REF] Serrano | Generalized triangulations, pipe dreams, and simplicial spheres[END_REF], synthesizing work in [START_REF] Billey | Some combinatorial properties of Schubert polynomials[END_REF][START_REF] Fomin | Reduced words and plane partitions[END_REF][START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF][START_REF] Woo | Catalan numbers and Schubert polynomials for w = 1(n + 1)[END_REF].

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 [START_REF] Soll | Type-B generalized triangulations and determinantal ideals[END_REF]. 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 × n × k box (and proved it as a lower bound). Their formula was subsequently proven non-bijectively by M. Rubey and C. Stump [START_REF] Rubey | Crossings and nestings in set partitions of classical types[END_REF]. 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. Examples of Theorems 1 and 2 are given in Figures 2, 3, and4. 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 [START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF]. C. Stump rephrased this bijection in Coxeter-theoretic language [START_REF] Stump | A new perspective on k-triangulations[END_REF], and a generalization of k-triangulations to all finite Coxeter groups was subsequently defined by C. Ceballos, J.-P. Labbé, and C. Stump [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF]. Their construction recovers k-triangulations in type A n and centrally symmetric k-triangulations in type B n .

Following [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF], 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 J (W, k) := J (Φ + (W ) × [k]) be the set of plane partitions of height k in the positive root poset Φ + (W ) (see Definition 15). In types H 3 and I 2 (m), we use D. Armstrong's surrogate "root posets" [START_REF] Armstrong | Generalized noncrossing partitions and combinatorics of Coxeter groups[END_REF].

Theorem 3 ([6, 32]) For W = A n , B n , H 3 , or I 2 (m) and k > 0, | S c (W, k)| = | J (W, k)|.
For W a finite Coxeter group, let R(W ) be the set of reduced words for the longest element w • , and if W is additionally a Weyl group then let L(W ) be the set of linear extensions of the positive root poset Φ + (W ). P. Edelman and C. Greene found a bijection between R(W ) and L(W ) in type A n , and M. Haiman proved the corresponding result in type B n (confirming a conjecture of R. Proctor) [START_REF] Edelman | Balanced tableaux[END_REF][START_REF] Haiman | Dual equivalence with applications, including a conjecture of Proctor[END_REF]. In the noncrystallographic types H 3 and I 2 (m), it was observed in [START_REF] Williams | Cataland[END_REF] that linear extensions of D. Armstrong's "root posets" also satisfy a similar bijection with R(W ).

Theorem 4 ( [START_REF] Edelman | Balanced tableaux[END_REF][START_REF] Haiman | Dual equivalence with applications, including a conjecture of Proctor[END_REF][START_REF] Stanley | On the number of reduced decompositions of elements of Coxeter groups[END_REF][START_REF] Williams | Cataland[END_REF]) For W = A n , B n , H 3 , or I 2 (m), there is a bijection between R(W ) and L(W ).

Ignoring redundancies like D 3 ∼ = 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 [START_REF] Williams | Cataland[END_REF]). 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 [START_REF] Billey | Some combinatorial properties of Schubert polynomials[END_REF] to induce P. Edelman and C. Greene's bijective proof of Theorem 4 into a bijective proof of Theorem 3 [START_REF] Woo | Catalan numbers and Schubert polynomials for w = 1(n + 1)[END_REF]. 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 [START_REF] Knutson | Subword complexes in Coxeter groups[END_REF][START_REF] Serrano | Generalized triangulations, pipe dreams, and simplicial spheres[END_REF]. 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) Theorem 3 , , / / R(A n ) Theorem 4 / / L(A n ) / / J (A n , k) . (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 [START_REF] Williams | Cataland[END_REF]. Our bijection is most easily explained using the cube of Figure 2, which displays the relationships between reduced words R, linear extensions L, subwords S, and plane partitions J of both type B n and for the parabolic quotient A n 2n-1 := A {sn} 2n-1 (see Definition 11 for the definitions of R, L, S, and J for A n 2n-1 ).

R(A n 2n-1 ) Fully commutative (C L R : Corollary 12) Little map (L R : Theorem 18) L(A n 2n-1 ) Rectification (R L : Theorem 16) R(B n ) Kraśkiewicz Insertion (K : Theorem 4) L(B n ) S(B n , k) No known bijection Theorem 2 J (B n , k) S(A n 2n-1 , k)
Fully commutative (C J S : Corollary 14)

Little map (L S : Proposition 21)

J (A n 2n-1 , k)
No known bijection Fig. 2: The bijections between R, L, S, and J for Bn and A n 2n-1 .

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) [START_REF] Williams | Cataland[END_REF].

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

KR : S(B n , k) / / R(B n ) K / / L(B n ) R L / / L(A n 2n-1 ) / / J (A n 2n-1 , k) , (2)
which-as with L. Serrano and C. Stump's type A n result [START_REF] Serrano | Generalized triangulations, pipe dreams, and simplicial spheres[END_REF]-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

LC : S(B n , k) L S / / S(A n 2n-1 , k) C J S / / J (A n 2n-1 , k) , (3)
which is based on the type B n Little map. We prove Theorem 2 by showing that LC is a bijection and also show that LC = KR.

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 | J (B n , k)| = | J (A n 2n-1 , k)| by interpreting each side as a representation of Lie algebras and then equating them with a branching rule [START_REF] Proctor | Shifted plane partitions of trapezoidal shape[END_REF], 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 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 n 2n-1 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.

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 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 π radians. We write Tri B (2n, k) for the set of all such T . The simplicial complex generated by all subsets of elements of Tri A (n, k) generalizes the type A n associahedron, which is obtained for Tri A (n+3, 1). In [START_REF] Jonsson | Generalized triangulations and diagonal-free subsets of stack polyominoes[END_REF], J. Jonsson enumerated Tri A (n, k). The centrally symmetric k-triangulations were introduced to generalize R. Simion's type B n associahedron; |Tri B (2n, k)| was conjectured in [START_REF] Soll | Type-B generalized triangulations and determinantal ideals[END_REF] and proven non-bijectively in [START_REF] Rubey | Crossings and nestings in set partitions of classical types[END_REF].

Theorem 6 ( [START_REF] Jonsson | Generalized triangulations and diagonal-free subsets of stack polyominoes[END_REF][START_REF] Rubey | Crossings and nestings in set partitions of classical types[END_REF]) The number of k-triangulations and centrally symmetric k-triangulations are given by

|Tri A (n+2k+1, k)| = 1≤i≤j≤n i + j + 2k i + j and |Tri B (2(n+k), k)| = k h=1 n i=1 n j=1 h + i + j -1 h + i + j -2 .
Our main theorem, Theorem 2, is therefore a bijective proof of this enumeration for 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 ∈ Z 2k+1 }, for some set of vertices v 0 , v 1 , . . . , 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 [START_REF] Pilaud | Multitriangulations as complexes of star polygons[END_REF]. 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 [START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF]. 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 [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF][START_REF] Stump | A new perspective on k-triangulations[END_REF].

Let (W, S) be a finite Coxeter system. A Coxeter element c = s π1 s π2 • • • s π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: Theorem 8 [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF][START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF] There are bijections between S(A n , k) and Tri A (n+2k+1, k), and between S(B n , k) and Tri B (2(n+k), k).

A n B n H 3 I 2 (m) s 1 s 2 • • • s n-1 s n s 0 4 s 1 • • • s n-2 s n-1 s 1 5 s 2 s 3 s 1 m s 2 For w ∈ W , a subword for w in a (possibly infinite) word a = a 1 a 2 a 3 • • • with a i ∈ S is a reduced word a i1 a i2 • • • a i for w such that i 1 < i 2 < • • • i . The c
In type A n , the bijection of Theorem 8 associates k-relevant edges with letters of c k w • (c). In type B n , the bijection associates k-relevant symmetric pairs of edges with letters. For example, see Figures 3 and4. For more details, see the excellent examples in [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF].

Correspondences for Fully Commutative Elements

This section briefly describes the square of Figure 2 containing the objects R(A n 2n-1 ), L(A n 2n-1 ), S(A n 2n-1 , k), and J (A n 2n-1 , k). Let (W, S) be a finite Coxeter system and for w ∈ W let R(w) be the set of reduced words in the simple generators S for w. Any two reduced words w, w ∈ R(w) may be transformed to each other using only braid moves-that is, the graph on R(w) with edges given by braid moves is connected. We say that w and w lie in the same commutation class if one may be transformed into the other using only commutations.

Definition 9 An element w ∈ 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) [START_REF] Stembridge | On the fully commutative elements of Coxeter groups[END_REF]. To see this, we construct its poset of join-irreducibles.

Fix w ∈ W and let w = w 1 • • • w be a reduced word for w, so that w i ∈ S and = (w) is the length of w. Define a partial order ≺ w on [ ] by the transitive closure of the relations i ≺ w j if i < j and w i w j = w j w i . This partial ordering defines a "root poset" Φ + (w) on [ ] called a heap [START_REF] Stembridge | On the fully commutative elements of Coxeter groups[END_REF][START_REF] Viennot | Heaps of pieces, I: Basic definitions and combinatorial lemmas[END_REF]. We may label the elements of Φ + (w) by replacing i by a i . If w, w are any two reduced words for a fully commutative element w, then it is not difficult to see that Φ + (w) and Φ + (w ) are isomorphic. We may therefore refer to the heap Φ + (w) of a fully commutative w ∈ W .

Recall that a linear extension of a finite poset P with elements is a bijection L : P → [ ] such that if p ≺ P p ∈ P, then L(p) < L(p ). The weak order interval [e, w] is now described by Φ + (w).

Theorem 10 ( [START_REF] Stembridge | On the fully commutative elements of Coxeter groups[END_REF]) For w fully commutative, there is a bijection between L(Φ + (w)) and R(w). This induces a bijection between J (Φ + (w)) and the elements in the interval [e, w].

Proof: The first statement is clear from the definitions: a linear extension L : Φ + (w) → [ ] corresponds to the reduced word i=1 w L -1 (i) . For the second statement, fix an order ideal I of Φ + (w), choose any linear extension L of Φ + (w) with initial part in I-that is, such that L(j) ≤ |I| for j ∈ I. The element in [e, w] corresponding to I is then

|I| i=1 w L -1 (i) . 2
We remark that Theorem 10 already gives us the flavor of a "combinatorial lift," since it uses the correspondence between L(Φ + (w)) and R(w) to induce a bijection between J (Φ + (w)) and [e, w].

Let J ⊆ 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 [START_REF] Björner | Combinatorics of Coxeter groups[END_REF]. For finite W , the parabolic quotient W J has a longest element w J

• and

W J is the interval [e, w J • ]. Definition 11 Let w {sn} • be the longest element of A n 2n-1 := A {sn} 2n-1 . We write R(A n 2n-1 ) := R(w {sn} • ), L(A n 2n-1 ) := L(Φ + (w {sn} • )), S(A n 2n-1 , k) := S(c k+n , w {sn} • ), J (A n 2n-1 , k) := J (Φ + (w {sn} • ) × [k]).
It is easy to check that Φ + (w

{sn} •
) is an n × n square-the inversions of w {sn} •

are the order filter in the root poset Φ + (A 2n-1 ) generated by the simple root α n . Since the element w {sn} • is fully commutative, Theorem 10 implies the following corollary [START_REF] Stembridge | On the fully commutative elements of Coxeter groups[END_REF].

Corollary 12 There is a bijection C L R between R(A n 2n-1 ) and L(A n 2n-1 ). We now explain the map between S(A n 2n-1 , k) and J (A n 2n-1 , k). Let w ∈ W be a fully commutative element, and fix a reduced word

w = w 1 w 2 • • • w with w i ∈ S. For such a w, let t w,i = w 1 • • • w i-1 w i w i-1 • • • w 1 . Let a = a 1 a 2 • • • a r
with a i ∈ S be a (possibly non-reduced) word in the simple reflections. For each letter w i of w, let a(i) := {j : j = i t for some 1 ≤ t ≤ in some w = a i1 • • • a i ∈ S(a, w) such that t w,i = t w ,j } be the set of letters of a corresponding to the letter w i of w in some subword of S(a, w). Since w is fully commutative, the set {a(i) : 1 ≤ i ≤ } does not depend on the initial choice w. Define the set of triples

Φ + (a, w) := {(i, a, b) : 1 ≤ i ≤ , a < b ∈ a(i) with no c ∈ a(i) for which a < c < b}.
We now endow Φ + (a, w) with a partial order given by the transitive closure of the relations (i, a, b) a (i, b, c) and (j, c, d) 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 a, and denote it by Φ + (a, w) [START_REF] Williams | Cataland[END_REF].

Theorem 13 ([32]) For w ∈ W fully commutative, there is a bijection between J (Φ + (a, w)) and S(a, w).

Proof: An order ideal I ∈ J (Φ + (a, w)) corresponds to the subword a i1 • • • a i of S(a, w), where for 1 ≤ j ≤ , we set i j := min ({a : (j, a, b) ∈ I} ∪ {max{b : (j, a, b) ∈ Φ + (a, w)}}) .

2

Since c = s 1 s 2 • • • s 2n-1 , w {sn} •
is fully commutative, and w {sn} • has the explicit reduced word

(s n • • • s 2n-1 )(s n-1 • • • s 2n-2 ) • • • (s 1 • • • s n ), Theorem 13

implies the following corollary.

Corollary 14 There is a bijection C J S between S(A n 2n-1 , k) and J (A n 2n-1 , k).

Reduced Words, Linear Extensions, and Little Bumps

This section describes the square of Figure 2 containing R(B n ), L(B n ), R(A n 2n-1 ), and L(A n 2n-1 ).

Reduced Words and Linear Extensions

This section provides more detail on the highly nontrivial Theorem 4. In particular, we describe the bijections between R(B n ) and L(B n ) and between R(A n ) and L(A n ). When w is not fully commutative, 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 [START_REF] Björner | Combinatorics of Coxeter groups[END_REF]). 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 ∈ S} and its positive roots [START_REF] Björner | Combinatorics of Coxeter groups[END_REF].

Definition 15

The root poset Φ + (W ) is the partial order on the positive roots of W defined by α < β iff α -β is a nonnegative linear combination of positive roots.

This relationship between the root poset and the longest element is examined in more detail in [START_REF] Williams | Cataland[END_REF][START_REF] Williams | Bijactions in Cataland[END_REF], where it is related to Catalan combinatorics (we note that Conjecture 4.4 of [START_REF] Williams | Bijactions in Cataland[END_REF] 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 L(W ) and R(W ). Under this bijection, the initial segments L -1 ({1, 2, . . . , i}) of a linear extension L and w • = a 1 a 2 • • • 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, | L(D 4 )| = 2400, but | R(D 4 )| = 2316. Kraśkiewicz insertion is the insertion procedure K : R(B n ) → L(B n ), due to W. Kraśkiewicz [START_REF] Kraśkiewicz | Reduced decompositions in hyperoctahedral groups[END_REF][START_REF] Lam | Bn Stanley symmetric functions[END_REF].

In [START_REF] Haiman | Dual equivalence with applications, including a conjecture of Proctor[END_REF], M. Haiman introduced a bijection called rectification between L(A n 2n-1 ) and L(B n ). Given a square tableau, which we prefer to think of as an element of L(A n 2n-1 ), one performs jeu-de-taquin slides until arriving at a tableau of trapezoidal shape, which we see as an element of L(B n ).

Theorem 16 ([9]

) There is a promotion-equivariant bijection R L : L(A n 2n-1 ) → L(B n ).

Little Bumps

D. Little introduced Little bumps in [START_REF] Little | Combinatorial aspects of the Lascoux-Schützenberger tree[END_REF]. 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 [START_REF] Lascoux | Schubert polynomials and the Littlewood-Richardson rule[END_REF]. 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 [START_REF] Hamaker | Relating Edelman-Greene insertion to the Little map[END_REF], and showed that Little bumps preserve the Q-tableau.

In [START_REF] Billey | Transition equations for isotropic flag manifolds[END_REF], 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 [START_REF] Billey | Coxeter-Knuth graphs and a signed Little map for type B reduced words[END_REF], 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. (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 b is the sequence {(w (j) ) -1 (i)} j=0 , and corresponds to the entries of the wiring diagram labeled i.

A type B Little bump B δ (i,j) on the reduced word b is specified by a covered reflection t (i,j) of w-an inversion of w such that (w • t (i,j) ) + 1 = (w)-and a direction δ ∈ {±1}. Given (i, j), identify the index p in which the inversion (i, j) is introduced in b. Set a = P δ (b, p), where the push P δ fixes b j for j = p and adds δ to b p . Here δ = δ if {w (p-1) (b p ), w (p-1) (b p + 1)} ∩ {i, j} = ∅ and δ = -δ otherwise. This condition ensures that the intersection of the trajectories of i and j in the wiring diagram is moved in the direction δ. Here, a may not be reduced, in which case there is a unique index p = p such that the word s a1 . . . s a p . . . s a is reduced (this follows from the assumption that t (i,j) was a covered reflection and Lemma 21 of [START_REF] Lam | A Little bijection for affine Stanley symmetric functions[END_REF]). Then a p and a p interchange the same values-up to sign-and we set a p := P δ (a, p ), iterating until we obtain a word a that is reduced. This algorithm is guaranteed to finish in finite time by [3, Lemma 3.5], and we set B δ (i,j) (b) = a. As observed in Section 4.1, for a ∈ R(A n 2n-1 ), the mixed insertion recording tableau L R (a) is in L(B n ), and coincides with its Kraśkiewicz recording tableau. Similarly, for b ∈ R(B n ), Theorem 4 implies that its Kraśkiewicz recording tableau also gives Q (b) ∈ L(B n ). Since these insertions are invertible, we obtain a bijection

L R : R(A n 2n-1 ) → R(B n ) by setting L R (a) = b when Q (a) = Q (b).
Theorem 17 tells us that the two reduced words a and b must be connected by a sequence of Little bumps. We now use the type B Little bumps to explicitly construct the bijection L R -1 : R(B n ) → R(A n 2n-1 ). Proposition 18 Define the sequences J k := (-1, 1), (1, 2), . . . , (k -1, k) with J 1 := (-1, 1), and let J be the concatenation J := J n , J n-1 , . . . , J 1 .

Then for b ∈ R(B n ),   (i,j)∈J B +1 (i,j)   b = a, where a ∈ R(A n 2n-1 ) and L R (a) = b.
Using techniques from [START_REF] Billey | Coxeter-Knuth graphs and a signed Little map for type B reduced words[END_REF], this proposition can be reduced to showing the map works as described for a single element of R(B n ), which can then be readily verified for the word c n . For example,

R(B 2 ) 0101 B +1 (-1,1) / / 1201 B +1 (1,2)
/ / 2301

B +1 (-1,1) / / 2312 ∈ R(A 2
3 ).

This Little map characterization provides more precise control over the relationship between a ∈ R(A n 2n-1 ) and L R (a) ∈ R(B n ). Recall that the peak set of a word a = a 1 • • • a r is the set Peak(a) := {i : a i-1 < a i > a i+1 }, while its descent set is Des(a) := {i : a i > a i+1 }. T-K. Lam showed that while a and Q (a) have the same peak set, in general they need not have the same descent set [START_REF] Lam | Bn Stanley symmetric functions[END_REF].

1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1
Fig. 3: From left to right, we have TriA(5, 1), S(A2, 1), and J (An, 1). The graph structure is given by flips. With the proper orientation, the graph at the left recovers the Tamari lattice on Dyck paths.

Lemma 19 Let a ∈ R(A n

2n-1 ). Then Des(a) = Des(L R (a)).

Proof: As observed in the proof of [START_REF] Billey | Coxeter-Knuth graphs and a signed Little map for type B reduced words[END_REF]Lemma 3.6], the only way the descent set can change is when the letter corresponding to the 1 in a consecutive 01 or 10 pattern is pushed to become a 0. The boundary of the (w j , w i )-crossing introduced by the mth inversion in the word a is the union of the trajectory of i from 0 to m and the trajectory of j from m to . The boundary of (w i , w j ) provides a lower bound for the possible locations of inversions in the Little bump B +1 (i,j) (see e.g. [START_REF] Billey | Coxeter-Knuth graphs and a signed Little map for type B reduced words[END_REF]Lemma 3.5]). Observe that the boundary of any bump (i, i + 1) is bounded below by the trajectory of i, which is in the upper half of the corresponding wiring diagram. The value 1 can only be decremented when the boundary is in the lower half of the wiring diagram. Since this never occurs, the descent set does not change under L R . 2

Subwords and Plane Partitions in Type A

We use the background of the previous sections to summarize Theorem 1. The core of L. Serrano and C. Stump's paper [START_REF] Serrano | Generalized triangulations, pipe dreams, and simplicial spheres[END_REF] is a bijective proof of an observation of S. Fomin and A. Kirillov [START_REF] Fomin | Reduced words and plane partitions[END_REF], generalizing work of A. Woo [START_REF] Woo | Catalan numbers and Schubert polynomials for w = 1(n + 1)[END_REF]. See also [START_REF] Billey | Some combinatorial properties of Schubert polynomials[END_REF][START_REF] Lenart | A unified approach to combinatorial formulas for Schubert polynomials[END_REF].

Theorem 1 ( [START_REF] Serrano | Generalized triangulations, pipe dreams, and simplicial spheres[END_REF][START_REF] Woo | Catalan numbers and Schubert polynomials for w = 1(n + 1)[END_REF]) There is an explicit bijection between Tri A (n + 2k + 1, k) and J (A n , k).

This bijection proceeds as follows. Let

N := n•(n+1) 2 = (w • ), a = a 1 a 2 • • • a k•n+N := c k w • (c)
, and let des a (i) be the number of descents in the word a 1 a 2 • • • a i . First, Tri A (n+2k+1, k) is encoded as S(A n , k) using Theorem 8. Next, using Theorem 4, we apply Edelman-Greene insertion to a subword a i1 a i2 • • • a i N of S(A n , k) to produce a linear extension in L(A n ). We modify this linear extension by replacing the letter j by des a (i j ) + 1, and-thinking of Φ + (A n ) as a tableau of staircase shape-subtract r from the rth row to obtain a plane partition of height at most k of staircase shape.

The construction above may be summarized as the "combinatorial lift" of Equation 1.

Remark 20 A recent result of J. Morse and A. Schilling may be phrased to state that for c = s 1 s 2 • • • s n the fixed Coxeter element of type A n and w ∈ A n , the subwords S(c k , w) may be given a crystal graph structure of type A k-1 [START_REF] Morse | Crystal operators and flag Gromov-Witten invariants[END_REF]. For example, in type A n with fundamental weights λ 1 , λ 2 , . . . , λ n , S(c n+1 , w • ) has a structure isomorphic to the crystal

A n (λ 1 + λ 2 + • • • + λ n ).
To connect these two stories, note that the subwords S(c k w • (c), w • ) in type A n are naturally a subset of the subwords S(c n+k , w • ). The bijection that J. Morse and A. Schilling provide between S(c n+k , w • ) 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.

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 Tri B (2(n+k), k) and J (A n 2n-1 , k). To define the lifting of the map L R : R(A n 2n-1 ) → R(B n ) to a map L S : S(A n 2n-1 , k) → S(B n , k), we will find it helpful to refer to a subword of S(A

n 2n-1 , k) = S((s 1 s 2 • • • s 2n-1 ) n+k , w {sn} •
) by

a i = a i1 1 a i2 2 • • • a i n 2 n 2 , where i j ∈ [n+k] records from which copy of (s 1 s 2 • • • s 2n-1 ) the simple reflection a i ∈ {s 1 , s 2 , • • • , s 2n-1 } was taken. We use the same notation for subwords of S(B n , k) = S((s 0 s 1 • • • s n-1 ) n+k , w • )-a sub- word is written b i = b i1 1 b i2 2 • • • b i n 2 n 2 , where i j ∈ [n+k] records from which copy of (s 0 s 1 • • • s n-1 ) the simple reflection b i ∈ {s 0 , s 1 , • • • , s n-1 } was taken. Proposition 21 Then the map L S : S(A n 2n-1 , k) → S(B n , k), defined by L S (a i1 1 a i2 2 • • • a i n 2 n 2 ) = b i1 1 b i2 2 . . . b i n 2 n 2 , where L R (a 1 a 2 • • • a n 2 ) = b 1 b 2 • • • b n 2 , is a bijection.
Proof: This follows from Lemma 19-the descent sets of a 1 a 2 • • • a n 2 and b 1 b 2 • • • 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 n 2n-1 , k) and S(B n , k), the map is well-defined. 2

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 = (w • ) and a = a 1 a 2 • • • a k•n+N := c k+n . First, Tri B (2(n+k), k
) is encoded as S(B n , k) using Theorem 8. Next, using Theorem 4, we apply Kraśkiewicz insertion K to a subword a i1 a i2 • • • a i N of S(B n , k) to produce a linear extension in L(B n ). At this point, rather than modify the linear extension of L(B n ), we next apply rectification R L to produce a linear extension in L(A n 2n-1 ), and only then do we modify the linear extension of L(A n 2n-1 ) by replacing the letter j by des a (i j ) + 1. Thinking of Φ + (A n 2n ) as a tableau of square shape, we subtract r from the rth 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 KR = 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 L(B n ) by replacing the letter j by des a (i j ) + 1, we do not have a bijection from the resulting tableaux to J (B n , k).

� � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �
Fig. 4: From left to right, we have TriB(6, 1), S(B2, 1), and J (A n 2n-1 , 1). The graph structure is given by flips.

Extensions

We close with some extensions and future directions. First, Proposition 21 can be adapted to give a bijection between S((s 0 s 1 ) in type A m+n-1 , from which we can then easily pass to plane partitions in an n × m × k box. Second, using the natural flip structure on S(B n , k) and our main theorem, we obtain a poset structure on plane partitions. It would be interesting to describe the flips directly on the plane partitions-this is open (and accessible) even for k = 1 (see also Figure 3 for a remark about this in type A, where the Tamari lattice on Dyck paths is recovered). Third, we do not have a good understanding of why the exact analogue of L. Serrano and C. Stump's type A n bijection does not work in type B n . Fourth, one can draw similar cubes to the one in Figure 2 in type A n , H 3 , and I 2 (m)-it would be interesting to provide analogues of all the edges of Figure 2 in those types. Fifth, the most obvious open problem is to complete either of the two edges in Figure 2 marked "No known bijection" (note that for k = 1 we know of several bijections and that some work has been done for k = 2). One approach towards this would be to extend the crystal structure of J. Morse and A. Schilling to subword complexes of other types as a first step towards a bijectivization of R. Proctor's proof that | J (B n , k)| = | J (A n 2n-1 , k)|.

Acknowledgments

The second author would like to thank Luis Serrano for helpful conversations and Phillipe Nadeau for comments on an early version of the abstract.

2 Fig. 1 :

 21 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.

Definition 7

 7 -sorting word w(c) of w is the lexicographically first (in position) reduced subword for w of the word c ∞[START_REF] Reading | Sortable elements and Cambrian lattices[END_REF]. Given w ∈ W and a possibly non-reduced word a = a 1 • • • a r with a i ∈ S, let S(a, w) be the set of subwords for w in a. Define S(W, k) := S(c k w • (c), w • ).

Theorem 17 (

 17 [START_REF] Billey | Coxeter-Knuth graphs and a signed Little map for type B reduced words[END_REF]) 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 ∈ [-n] ∪ [n], j ∈ [n] and |i| ≤ j. For w ∈ B n let s b1 • • • s b ∈ R(w) with corresponding word b = b 1 • • • b with b i ∈ {0,1, . . . , n-1}we abuse notation by associating b with s b1 • • • s b . Let w (m) = s b1 • • • s bm with w (0) the identity. The wiring diagram of b is the diagram on {0, 1, . . . , } × Z \ {0} where

  • • • s n-1 ) m+k , (s 0 s 1 • • • s n-1 ) m ) in type B n and S((s 1 • • • s m+n-1 ) m+k , w

	{sm}
	•

Z.H. is supported by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.


Svetlana Poznanović

Catherine H Yan
email: cyan@math.tamu.edu.

Maximal increasing sequences in fillings of almost-moon polyominoes

Keywords: moon polyominoes, maximal chains, 01-fillings

It was proved by Rubey that the number of fillings with zeros and ones of a given moon polyomino that do not contain a northeast chain of a fixed size depends only on the set of column lengths of the polyomino. Rubey's proof uses an adaption of jeu de taquin and promotion for arbitrary fillings of moon polyominoes and deduces the result for 01-fillings via a variation of the pigeonhole principle. In this paper we present the first completely bijective proof of this result by considering fillings of almost-moon polyominoes, which are moon polyominoes after removing one of the rows. More precisely, we construct a simple bijection which preserves the size of the largest northeast chain of the fillings when two adjacent rows of the polyomino are exchanged. This bijection also preserves the column sum of the fillings. In addition, we also present a simple bijection that preserves the size of the largest northeast chains, the row sum and the column sum if every row of the filling has at most one 1. Thereby, we not only provide a bijective proof of Rubey's result but also two refinements of it.

Résumé. Rubey a montré que le nombre de remplissages d'un polyomino lunaire donné par des zéros et des uns qui ne contiennent pas de chaîne nord-est d'une taille fixée ne dépend que de l'ensemble des longueurs des colonnes du polyomino. La preuve de Rubey utilise une adaptation du jeu de taquin et de la promotion sur des remplissages arbitraires de polyominos lunaires et déduit le résultat pour les remplissages 0/1 par inclusion-exclusion. Dans cet article, nous présentons la première preuve bijective de ce résultat en considérant des remplissages de polyominos presque lunaires, qui sont des polyominos lunaires dont on a supprimé une ligne. Plus précisément, nous construisons une bijection simple qui préserve la taille de la plus longue chaîne nord-est des remplissages lorsque deux lignes adjacentes du polyomino sont échangées. Cette bijection préserve aussi la somme des colonnes des remplissages. En outre, nous présentons aussi une bijection simple qui préserve la taille de la plus longue chaîne nord-est, la somme des lignes et la somme des colonnes si chaque ligne du remplissage contient au plus un 1. Nous fournissons donc non seulement une preuve bijective du résultat de Rubey, mais aussi deux raffinements de celui-ci.

Introduction

In [START_REF] Chen | Crossings and nestings of matchings and partitions[END_REF], Chen, Deng, Du, Stanley, and Yan used Robinson-Schensted-like insertion/deletion processes to show the symmetry between the sizes of the largest crossings and the largest nestings in set partitions. These results have been generalized and put in a larger context of enumeration of fillings of boards where one imposes restrictions on the increasing and decreasing chains of the fillings [START_REF] Krattenthaler | Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes[END_REF]. Moon polyominoes are polyominoes that are convex and intersection-free. In a moon polyomino M the lengths of rows (and columns) are arranged in a unimodal order. Let F N (M, n) be the set of assignments of nonnegative integers to the cells of M such that the sum of the integers equals n and let F 01 (M, n) be the subset of F N (M, n) where the cells may only be filled with zeros and ones. Let ne(M ) be the length of the longest strict northeast chain in a filling M . The motivation for this paper is the very important result of Rubey [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF] that the cardinalities of the sets {M : M ∈ F N (M, n) and ne(M ) = k} and {M : M ∈ F 01 (M, n) and ne(M ) = k} only depend on the multiset of column lengths of the moon polyomino M. This is a very interesting property for fillings of moon polyominoes: many combinatorial statistics are invariant under permutations of rows (or columns). For example, a similar statement is also known for the major index introduced by Chen, Poznanović, Yan and Yang [START_REF] Chen | Major index for 01-fillings of moon polyominoes[END_REF], for the numbers of northeast and southeast chains of length 2 studied by Kasraoui [START_REF] Kasraoui | Ascents and descents in 01-fillings of moon polyominoes[END_REF], and for various analogs and generalizations of 2-chains [START_REF] Chen | Mixed statistics on 01-fillings of moon polyominoes[END_REF][START_REF] Wang | Positive and negative chains in charged moon polyominoes[END_REF] .

The aforementioned result of Rubey is a culmination of the work of several people who proved it for various subclasses of moon polyominoes. The case for Ferrers and reverse Ferrers shapes was proved bijectively by Krattenthaler [START_REF] Krattenthaler | Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes[END_REF] using Fomin's growth diagrams [START_REF] Fomin | The generalized Robinson-Schensted-Knuth correspondence[END_REF][START_REF] Fomin | Duality of graded graphs[END_REF][START_REF] Fomin | Schensted algorithms for dual graded graphs[END_REF]. Jonsson, motivated by the problem of counting generalized triangulations with a given size of the maximal crossings, first proved the result for maximal 01-fillings of stack polyominoes using an involved induction [START_REF] Jonsson | Generalized triangulations and diagonal-free subsets of stack polyominoes[END_REF] , and later with Welker [START_REF] Jonsson | A spherical initial ideal for Pfaffians[END_REF] for all 01-fillings with a fixed number of 1's using the machinery of simplicial complexes and commutative algebra. A stack polyomino is a convex polyomino in which the rows are arranged in a descending order from top to bottom. A bijective proof for the general case of N-fillings of moon polyominoes was obtained by Rubey [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF] using an adaptation of jeu de taquin and promotion. Rubey additionally deduced the statement for F 01 (M, n) using inclusion-exclusion. Later, a bijective proof for F 01 (M, n) with the additional assumption that n is maximal was provided by Serrano and Stump [START_REF] Serrano | Maximal fillings of moon polyominoes, simplicial complexes, and Schubert polynomials[END_REF] for the special case of Ferrers shapes and extended to stack polyominoes by Rubey [START_REF] Rubey | Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs[END_REF]. Other papers that are part of this whole picture but phrase the results in terms of avoiding patterns are [START_REF] Backelin | Wilf-equivalence for singleton classes[END_REF][START_REF] Bloom | Modified growth diagrams, permutation pivots, and the BWX map φ[END_REF][START_REF] Bousquet-Mélou | Decreasing subsequences in permutations and Wilf equivalence for involutions[END_REF][START_REF] De Mier | k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams[END_REF].

In this paper we give a bijective proof of Rubey's result for F 01 (M, n) [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF]. In fact, we construct two simple bijections for 01-fillings demonstrating two different refinements of this result. For a moon polyomino M, let σM be another moon polyomino obtained by permuting the rows of M. Inspired by the work on layer polyominoes [START_REF] Phillipson | 2-Chains in 01-fillings of layer polyominoes[END_REF], our idea is to extend the class of moon polyominoes to a more general family that would allow us to transform the moon polyomino M to any σM by a sequence of steps that interchange two adjacent rows at each time. For this purpose we introduce the notion of almost-moon polyominoes, which become moon polyominoes after removing one of its rows (see Section 2 for the exact definition). Let M and N be two almost-moon polyominoes that are related by an interchange of two adjacent rows. We present two bijections. The first is a map φ M,N from 01-fillings of M to those of N which preserves the number of non-zero entries, the size of the longest northeast chain and the column sums. The second map ψ M,N is restricted to fillings in which every row has at most one 1 and preserves the size of the longest northeast chains, the row sum, and the column sum. Both our maps are simple to describe but the proofs that they have the desired properties are technical; we omit them here and refer the reader to the full version of the paper [START_REF] Poznanović | Maximal increasing sequences in fillings of almost-moon polyominoes[END_REF].

The paper is organized as follows. Section 2 contains the necessary notation and the statements of the main results. In Section 3 we construct the bijection φ M,N for fillings of almost-moon polyominoes which preserves the size of maximal northeast chains and the column sums. In Section 4 we restrict to fillings that have at most one 1 in each row and describe the bijection ψ M,N . We conclude the paper with some comments and counterexamples to a few seemingly natural generalizations in Section 5.

Notation and statements of the main results

A polyomino is a finite subset of Z 2 , where we represent every element (i, j) of Z 2 by a square cell. The polyomino is row-convex (column-convex) if its every row (column) is connected. If the polyomino is both row-and column-convex, we say that it is convex. It is intersection-free if every two columns are comparable, i.e., the row-coordinates of one column form a subset of those of the other column. Equivalently, it is intersection-free if every two rows are comparable. A moon polyomino is a convex intersection-free polyomino (e.g. Figure 1a). The length of a row (or a column) is the number of cells in it. Note that in a moon polyomino the lengths of rows from top to bottom form a unimodal sequence. We will say that a row R is an exceptional row of a polyomino M if there are rows above R and below R with larger lengths in M. An almost-moon polyomino is a polyomino with comparable convex rows and at most one exceptional row (e.g. Figure 1b). Therefore, every moon polyomino is also an almost-moon polyomino and an almost-moon polyomino is not necessarily column-convex. In this paper we will consider polyominoes whose cells are filled with zeros and ones. A northeast chain, or shortly ne-chain, of size k in such a filling is a set of k cells {(i 1 , j 1 ), (i 2 , j 2 ), . . . ,

(i k , j k )} with i 1 < • • • < i k , j 1 < • • • < j k filled with 1's such that the k × k submatrix G = {(i r , j s ) : 1 ≤ r ≤ k, 1 ≤ s ≤ k}
is contained in the polyomino (with no restriction on the filling of the other cells). See Figure 2 for an illustration. We will call the ne-chains of size k shortly k-chains. Note that in a moon polyomino M, k 1-cells in a northeast direction satisfy the submatrix condition if and only if the corners (i 1 , j k ) and (i k , j 1 ) are contained in M, which is equivalent to the whole rectangle determined by these corners being contained in M. In an almost-moon polyomino, the submatrix condition is satisfied if and only if the vertices (i 1 , j k ) and (i k , j 1 ) either determine a rectangle which is completely contained in M or an almost-rectangle with one exceptional row contained in M. In the latter case, the exceptional row does not contain any elements from the ne-chain. For a 01-filling M of an almost-moon polyomino, we denote by ne(M ) the size of its largest ne-chains. Suppose that M has k rows and columns and let r ∈ N k and c ∈ N . We will denote by F(M) the set of all 01-fillings of M, by F(M, n) those fillings with exactly n 1's, and by F(M, r, c) the set of all 01-fillings with row sums given by r and column sums given by c. Our first main result states that if M and N are two almost-moon polyominoes related by an interchange of adjacent rows (e.g. Figure 1), then the statistic ne is equidistributed over the sets F(M, * , c) and F(N , * , c) of fillings of M and N , respectively, with fixed column sums but arbitrary row sums:

M ∈F (M, * ,c) q ne(M ) = M ∈F (N , * ,c) q ne(M ) .
More precisely, we have the following theorem.

Theorem 1 Let M and N be two almost-moon polyominoes such that N can be obtained from M by an interchange of two adjacent rows. In addition assume that M and N have no exceptional rows other than the swapped ones. Then there is a bijection

φ M,N : F(M) -→ F(N )
that preserves the column sums of the fillings and such that ne(φ M,N (M )) = ne(M ) for M ∈ F(M).

Moreover, φ N ,M • φ M,N = 1 F (M) .
Let M be an almost-moon polyomino with k rows, σ ∈ S k , and suppose the polyomino σM obtained by permuting the rows of M according to σ is also an almost-moon polyomino. Note that σM can also be obtained by a sequence of steps in which only two adjacent rows are interchanged. Moreover, the order of steps can be chosen so that the intermediate polyominoes are all almost-moon polyominoes with no exceptional rows other than the swapped ones. In other words, the set of all σM which are almost-moon polyominoes is connected by transposition of adjacent rows. One way to see this is to note that one can reach the polyomino in which the row lengths are descending from top to bottom by starting from M and first moving its exceptional row down until there is no longer rows below it, then moving the shortest row of M to the bottom, the second shortest row to the second position from below, etc. Consequently, by composing the maps from Theorem 1 we get the following corollary.

Corollary 2 Let M be an almost-moon polyomino with k rows and columns, σ ∈ S k be a permutation of the row indices such that σM is also an almost-moon polyomino. Let c ∈ N . Then there is a bijection φ : F(M, * , c) -→ F(σM, * , c) such that ne(φ(M )) = ne(M ) for M ∈ F(M, * , c). Moreover, the size of {M : M ∈ F(M, n), ne(M ) = k} depends only on the multiset of column lengths of M.

Proof: To prove the second part of the statement, suppose M 1 is the moon polyomino with descending row lengths that can be obtained by reordering the rows of M as in the discussion above. Suppose that the same procedure applied to the transpose M t 1 of M 1 yields the polyomino M 2 with descending row lengths. Then M 2 is a Ferrers shape and it depends only on the set of column lengths of M. Since the transpose of ne-chains are also ne-chains, it follows from the first part that the size of {M : M ∈ F(M, n), ne(M ) = k} also depends only on the set of lengths of the columns of M.

The fact that |{M

: M ∈ F(M, * , c), ne(M ) = k}| = |{M : M ∈ F(σM, * , c), ne(M ) = k}| if M
and σM are moon polyominoes as well as the second part of Corollary 2 was proved using a variation of the pigeonhole principle by Rubey [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF]. Therefore, our results provide a bijective proof of these facts and extend them to a larger set of polyominoes in which these properties hold. In Section 5 we discuss why this extension is in a sense the best possible.

As discussed in [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF], one cannot hope to simultaneously preserve both r and c, i.e., the natural generalization |{M : M ∈ F(M, r, c), ne(M ) = k}| = |{M : M ∈ F(σM, σr, c), ne(M ) = k}| does not hold. However, our second main result implies that ne can be preserved together with both the row and the column sums if the fillings are restricted to have at most one 1 in each row.

Theorem 3 Let M and N be two almost-moon polyominoes such that N can be obtained from M by an interchange of two adjacent rows. In addition assume that M and N have no exceptional rows other than the swapped ones. If r ∈ {0, 1} * and c ∈ N * , then there is a bijection

ψ M,N : F(M, r, c) -→ F(N , r , c) such that ne(ψ M,N (M )) = ne(M ) for M ∈ F(M, r, c
), where r is obtained from r by exchanging the entries corresponding to the two swapped rows.

This theorem was proved for moon polyominoes by Rubey [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF]. By the same discussion after Theorem 1 and a combination of the maps ψ M,N and φ M,N , we get the following corollary.

Corollary 4 Let M be an almost-moon polyomino with k rows and columns, σ ∈ S k be a permutation of the row indices such that σM is also an almost-moon polyomino. Let r ∈ {0, 1} k and c ∈ N l . Then there is a bijection ψ : F(M, r, c) -→ F(σM, σr, c) such that ne(ψ(M )) = ne(M ) for M ∈ F(M, r, c). Moreover, the number of fillings M ∈ F(M, r) with at most one 1 per row and fixed column sums depends only on the multiset of column lengths of M.

Maximal increasing sequences in 01-fillings with fixed total sum

In this section we will describe the maps φ M,N and prove Theorem 1. To this end, let M and N be two almost-moon polyominoes related by an interchange of two adjacent rows (e.g. Figure 1). Assume that M and N have no exceptional rows other than the swapped ones. If the swapped rows are of equal length then M = N and we define φ M,N to be the identity map on F(M).

Otherwise, suppose the lengths of the swapped rows are not equal and let R s and R l , respectively, be the shorter and longer rows. Note that M\R s and N \R s have no exceptional rows. Let α, β, γ, δ be the fillings of the regions of R s and R l in M as depicted on the left side of Figure 3. Precisely, α is the filling of the shorter row R s , β is the filling of the part of the longer row R l which has the same column support as row R s , and γ and δ are the fillings of the two ends of row R l so that the whole filling of row R l viewed as a binary string is a concatenation of γ, β, and δ. Note that one of γ and δ may be the empty string. First we define a map f M,N : F(M) -→ F(N ) as follows.

Definition 5 Using the notation above, f M,N (M ) is the filling of N in which (1) the filling of the rows in N other than R s and R l is the same as in M (2) the filling of the shorter row R s of N is β (3) the filling of the longer row R l of N is the concatenation of γ, α, and δ.

See Figure 3 for an illustration.

α β γ δ R s R l f M,N α β γ δ R l R s
Fig. 3: The fillings M and f M,N (M ) differ only in the rows R s and R l .

Lemma 6 f N ,M • f M,N = 1 F (M) .
If it is clear what the polyominoes M and N are, we will leave out the subscripts and write only f (M ).

Lemma 7 If the almost-moon polyominoes M and N are related by an interchange of the rows R s and R l as above, then for every

M ∈ F(M), |ne(M ) -ne(f M,N (M ))| ≤ 1.
Therefore, every filling M ∈ F(M) satisfies exactly one of the following 3 conditions:

(I) ne(f (M )) = ne(M ) (II) ne(f (M )) = ne(M ) + 1 (III) ne(f (M )) = ne(M ) -1.
Let F I (M), F II (M ), and F III (M), be the fillings of M that satisfy the conditions (I), (II), and (III), respectively. Below we describe how φ M,N (M ) is defined on each of these three sets. Case I. For M ∈ F I (M) we define φ M,N (M ) = f M,N (M ). It is clear that this defines a bijection from F I (M) onto F I (N ).

Case II. For M ∈ F II (M) with ne(M ) = k, we have ne(N ) = k + 1 where N = f (M ). Reasoning as in the proof of Lemma 7, one can see that all (k + 1)-chains in N contain exactly one cell from R s ∪ R l and that that cell must be in the part α of the longer row R l of N (see the right filling in Figure 3).

Definition 8 Suppose M ∈ F II (M) and ne(f (M )) = ne(M ) + 1 = k + 1. The 1-cells in row R l of f (M ) which are part of a (k + 1)-chain are called problem cells.
Let α 0 be the set of problem cells in N = f (M ) and let β 0 be the set of cells in row R s of N that share a horizontal edge with the problem cells. We define φ M,N (M ) to be the filling N of N obtained by replacing the problem cells in α 0 by zeros and the cells in β 0 by ones. In other words, φ M,N (M ) = N is obtained by a vertical shift of the problem cells in N from row R l to row R s .

Case III. For M ∈ F III (M), we have f M,N (M ) ∈ F II (N ). In this case we set φ

M,N (M ) = f M,N (φ N ,M (f M,N (M ))).
It is clear that the map ψ M,N is well-defined and preserves the statistic ne. In addition, ψ M,N and ψ N ,M are inverse to each other.

We remark that the map ψ M,N is different from the restriction of φ M,N on the set F(M, r, c). Namely, φ M,N does not always preserve the row sum, hence not necessarily maps fillings of F(M, r, c) to F(N , r , c) when r ∈ {0, 1} * .

Concluding remarks

We conclude this paper with some comments and counterexamples to a few seemingly natural generalizations of Theorem 1 and 3.

Symmetry of (ne, se) for fillings with r ∈ {0, 1} * . A southeast chain, or shortly se-chain, of size k in a 01-filling M is a set of k cells {(i 1 , j k ), (i 2 , j k-1 ), . . . ,

(i k , j 1 )} with i 1 < • • • < i k , j 1 < • • • < j k filled with 1's such that the k × k submatrix G = {(i r , j s ) : 1 ≤ r ≤ k, 1 ≤ s ≤ k} is contained in the polyomino.
We denote by se(M ) the size of the largest se-chains of M . By the symmetry of ne and se we have that Lemma 9 also holds for se.

It is known that in 01-fillings of a Ferrers shape with fixed row sum and column sum in N, the pair (ne, se) may not be symmetrically distributed (e.g. see [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF][START_REF] De Mier | On the symmetry of the distribution of crossings and nestings in graphs[END_REF]). On the other hand, when both r, c ∈ {0, 1} * , (ne, se) does have a symmetric joint distribution. This was proved for Ferrers shapes by Krattenthaler [START_REF] Krattenthaler | Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes[END_REF] and for moon polyominoes by Rubey [START_REF] Rubey | Increasing and decreasing sequences in fillings of moon polyominoes[END_REF].

The above results raise the question whether for almost-moon polyominoes the pair of statistics (ne, se) has a symmetric joint distribution when one or both of r, c are in {0, 1}, and whether the distribution of (ne, se) is unchanged when one swaps two adjacent rows.

Surprisingly, the answers are all negative. In the following we give two sets of counterexamples. The first one is for the case that r ∈ {0, 1} * but c ∈ N. The involved polyominoes are of small sizes, and we can list all the fillings explicitly. The second one is for the case when both r and c are in {0, 1}. We found the counterexample by running a computer program, and we will just describe the results without listing all the details.

(1, 3) Figure 4 shows that even for moon polyomino with r ∈ {0, 1} * but c ∈ N * , the distribution of (ne, se) is not necessarily symmetric. Figure 5 gives an example that the distribution of the pair (ne, se) is not preserved when two adjacent rows are swapped in an almost-moon polyomino. Note that the first two fillings (M, M ) in Figure 5 are coupled fillings, whose corresponding coupled fillings are the first two M, (1, 3)

• • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (3, 2) • • • • (2, 1) • •
• • • • M , (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (3, 2) • • • • (2, 1) • • • • • • • • N, (2, 3) • • • • N , (1, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (2, 2) • • • • (3, 1) • • • • (2, 2)

Example 11

Our second example is restricted to 01-fillings where each row as well as each column has exactly one 1. We say that such fillings are restricted. Let M 1 , M 2 and M 3 be the polyominoes whose cells are given by

M 1 = {(i, j) : 1 ≤ i ≤ 6, 1 ≤ j ≤ 6} -{(1, 6)}. M 2 = {(i, j) : 1 ≤ i ≤ 6, 1 ≤ j ≤ 6} -{(1, 5)}. M 3 = {(i, j) : 1 ≤ i ≤ 6, 1 ≤ j ≤ 6} -{(1, 4)}.
Each polyomino has 600 restricted fillings. Let G 1 (x, y) = M x ne(M ) y se(M ) be the joint distribution of (ne, se) over restricted fillings of M 1 . Similarly define G 2 (x, y) and G 3 (x, y) for restricted fillings in M 2 and M 3 . With the help of a computer program we obtained G 1 (x, y) = G 2 (x, y) = xy 5 + x 5 y + 72(x 2 y 4 + x 4 y 2 ) + 48(x 3 y 4 + x 4 y 3 ) +50(x 2 y 3 + x 3 y 2 ) + 8(x 2 y 5 + x 5 y 2 ) + 242x 3 y 3

and G 3 (x, y) = xy 5 + x 5 y + 72x 2 y 4 + 73x 4 y 2 + 48x 3 y 4 + 47x 4 y 3 +50x 2 y 3 + 49x 3 y 2 + 8x 2 y 5 + 8x 5 y 2 + 243x 3 y 3 .

Equation ( 2) is symmetric with respect to x, y, which is expected for M 1 since it is a moon polyomino. Equation [START_REF] Bousquet-Mélou | Decreasing subsequences in permutations and Wilf equivalence for involutions[END_REF] shows that the joint distribution of (ne, se) over almost-moon polyominoes is not necessarily symmetric, even if we require that every row and every column has exactly one 1. The difference between the two equations implies that the distribution of (ne, se) may not be preserved when two adjacent rows are swapped.

Coupled fillings with arbitrary row sums. Another natural question is whether we can extend the idea of coupling in Theorem 3 to construct a bijection for Theorem 1. The following example shows that the direct application does not work.

Example 12 Consider fillings in F(M, * , c) where a row may have multiple 1s. For a filling M of M, we couple with it the filling M obtained from M by swapping the fillings α and β, just as what we did in Section 4. Again let N = f M,N (M ) and N = f M,N (M ). In the fillings shown in Figure 6, ne(M ) = 3, ne(M ) = 4 while ne(N ) = ne(N ) = 4. Lemma 9 does not hold for this case. It is still open whether Theorem 3 holds for the family of fillings for which r ∈ N * but c ∈ {0, 1} * We point out that Lemma 9 does not hold in this case either. Given a filling M with multiple 1-cells in a row, the natural way to define the coupling with the same row sum is to let M be obtained from M by keeping the empty columns of α ∪ β and reversing the fillings in the remaining columns of α ∪ β. Then (N, N ) are obtained from (M, M ) by exchanging the two rows R s and R l with their fillings. Example 13 The fillings in Figure 7 gives an example where ne(M ) = 2, ne(M ) = 3 while ne(N ) = ne(N ) = 3.

• • • • • • • • M • • • • • • • • M • • • • • • • • N • • • • • • • • N
• • • • • • • • M • • • • • • • • M • • • • • • • • N • • • • • • • • N
Northeast chains in fillings of general polyominoes. It is natural to ask whether Theorem 1 or Theorem 3 can be extended to a more general family of polyominoes. The following example shows that if there are several exceptional rows in the polyomino, then the distribution of ne(M ) may not be the same after a swap of two adjacent rows.

Example 14 This example was first given in [START_REF] Phillipson | 2-Chains in 01-fillings of layer polyominoes[END_REF] for layer polyominoes, which are polyominoes that are row-convex and row-intersection-free. The right polyomino in Figure 8 is almost-moon but the left one is not. Let G(x, F) = M ∈F x ne(M ) be the generating function for the statistic ne over the fillings in a set F. First consider 01-fillings where every row and every column has exactly one 1. We obtained the following generating functions. For the left polyomino M 1 , G(x, F(M 1 , r, c)) = x + 37x 2 + 31x 3 + 3x 4 , while for the right polyomino M 2 , G(x, F(M 2 , r, c)) = p + 36x 2 + 32x 3 + 3x 4 , where r = c = (1, 1, 1, 1, 1). This provides a counterexample of Theorem 3 for general polyominoes.

M 1 M 2
Fig. 8: Two general polyominoes related by an interchange of two adjacent rows.

The above example also implies that Theorem 1 can not hold for general polyominoes. Namely, take the same two polyominoes and consider all the fillings in which each column has exactly one 1, but there is no constraint on the row. Note that (1) empty rows do not affect the statistic ne and can be ignored and ( 2

Fig. 1 :

 1 Fig.1:A moon polyomino and an almost-moon polyomino with an exceptional row R that differ by an interchange of adjacent rows.

Fig. 2 :

 2 Fig. 2: A 01-filling M of an almost-moon polyomino with ne(M ) = 3. The 1's are represented by dots and the 0-cells are drawn empty. The circled dots form the only 3-chain in M .

Fig. 4 :

 4 Fig. 4: Fillings of a moon polyomino with r = (1, 1, 1, 1) and c = (2, 1, 1).

Fig. 5 :

 5 Fig. 5: Fillings of almost-moon polyominoes. The first row is for an almost-moon polyomino M, and the second row is for N which differ from M by swapping the second and the third rows.

Fig. 6 :

 6 Fig. 6: Coupled fillings in F(M, r, c) with r ∈ N * and r ∈ {0, 1} * . The circled dots form 4-chains in the polyominoes.

Fig. 7 :

 7 Fig. 7: Coupled fillings in F(M, r, c) with r ∈ N * and c ∈ {0, 1} * .

  ) any sub-polyomino of M 1 or M 2 containing three rows is an almost-moon polyomino. By Theorem 1 rearranging rows for such three-row polyominoes does not change the distribution of ne(M ) over F(M, * , c).Now let c = (1, 1, 1, 1, 1). We have1. Either G(ne, F(M 1 , * , c)) = G(ne, F(M 2 , * , c))and we have the desired counterexample, or 2. G(ne, F(M 1 , * , c)) = G(ne, F(M 2 , * , c)). But then the example from the previous paragraph implies that the distribution of ne over 01-fillings in F(M 1 , * , c) and F(M 2 , * , c) with empty rows are different. Note that the set of fillings of a polyomino M with empty rows can be obtained as the union of set F i (M, r, c), which consists of fillings in which the i-th row is empty. An application of the inclusion-exclusion principle implies that there is a sub-polyomino N 1 of M 1 consisting of 4 rows such that G(ne, F(N 1 , * , c)) = G(ne, F(N 2 , * , c)) where N 2 is the sub-polyomino of M 2 consisting of the same four rows as in N 1 .

The first author is partially supported by NSF grant DMS-1312817. The second author is partially supported by NSF grant DMS-1161414.

1365-8050

Although the description of the map φ M,N is simple, the proof that it is a well-defined bijection from F(M, * , c) to F(N , * , c) preserving the statistic ne is rather technical and we omit it here. It would be interesting to see whether there is a relationship between the Edelman-Greene bijection as used in [START_REF] Serrano | Maximal fillings of moon polyominoes, simplicial complexes, and Schubert polynomials[END_REF][START_REF] Rubey | Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs[END_REF] and the map on moon polyominoes induced by the φ M,N 's. The analogous question for the Robinson-Schensted map as used in [START_REF] Krattenthaler | Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes[END_REF] and the BWX map was answered by Bloom and Saracino [START_REF] Bloom | Modified growth diagrams, permutation pivots, and the BWX map φ[END_REF].

Maximal increasing sequences in fillings with restricted row sum

In this section we restrict to fillings with at most one 1 in each row and prove Theorem 3. Explicitly, let M and N be two almost-moon polyominoes that can be obtained from each other by an interchange of two adjacent rows. Assume that M and N have no exceptional rows other than the swapped ones. Let r ∈ {0, 1} * and c ∈ N * , we shall construct a bijection ψ M,N from F(M, r, c) to F(M, r , c) that preserves the size of the largest ne-chains, where r is obtained from r by exchanging the entries corresponding to the two swapped rows.

If the two swapped rows are of equal length, then M = N and we can simply take ψ M,N to be the identity map. In the following, we assume that the two swapped rows are R s and R l , where the length of R s is smaller than that of R l . We keep the notations as in the previous section. For any filling M let α, β, γ, δ be as defined in Figure 3. Note that for M ∈ F(M, r, c), there is at most one 1 in α, as well as in the union of β, γ and δ. Define the filling coupled with M to be the filling M of M which is obtained from M by exchanging the fillings α and β. Let N (resp. N ) be obtained from M (resp. M ) by swapping the rows R s and R l together with their fillings. In other words, N = f M,N (M ) and N = f M,N (M ). Clearly N and N are fillings coupled with each other.

We need the following lemma, which is the crucial observation for the construction of ψ M,N . Lemma 9 Let fillings (M, M ) be a pair of fillings in F(M, r, c) coupled with each other and let (N, N ) = (f M,N (M ), f M,N (M )) be fillings of N . Then ne(M ) = ne(N ) or ne(M ) = ne(N ).

Lemma 9 implies that {ne(M ), ne(M )} = {ne(N ), ne(N )}

as multisets. To see this, note that if ne(N ) = ne(N ) = k, then applying Lemma 9 to both M and M yields ne(M ) = ne(M ) = k. Otherwise, if ne(N ) = ne(N ), then applying Lemma 9 to N, N yields that one of ne(M ), ne(M ) equals ne(N ), and the other equals ne(N ). Equation (1) allows us to construct an ne-preserving bijection between the pairs of coupled fillings {M, M } and {N, N }. Combining the bijections of all the coupled fillings we get the desired map ψ M,N . Explicitly, we can describe the map ψ M,N as follows:

Let M be a filling in F(M, r, c).

1. If either α or β has no 1, then let ψ M,N (M ) = N , the filling of N obtained by swapping the two rows together with their fillings.