# Generalized triangulations, pipe dreams, and simplicial spheres.

1 Introduction

Fix positive integers n and k such that 2k < n. A k-triangulation of a convex n-gon is a maximal collection of diagonals in the n-gon such that no k + 1 diagonals mutually cross. A k-fan of Dyck paths of length 2l is a collection of k Dyck paths from (0,0) to (l, l) which do not cross (although they may share edges).

The following theorem is the first main result in this article. It extends results by S. Elizalde [Eli07] and C. Nicolas [Nic09].

Theorem 1.1 There is an explicit bijection between k-triangulations of a convex n-gon and k-fans of Dyck paths of length 2(n - 2k).

A north-east chain of length l in a Ferrers shape [lambda] is a sequence of [lambda] boxes in A such that every box in the sequence is strictly north and strictly east of the preceding one, and for which the smallest rectangle containing all boxes in the sequence is also contained in [lambda]. A k-north-east filling of [lambda] is a (0,1)- filling which does not contain any north-east chain of 1's of length k + 1, and in which the number of 1's is maximal. As usual, we identify a (0,1)-filling with its set of boxes filled with 1's and draw them by marking its set of boxes by +'s. See Figure 1(a) for an example. The set of all k-north-east fillings of [lambda] is denoted by [F.sub.NE] ([lambda], k). South-east chains, k-south-east fillings and [F.sub.SE] ([lambda], k) are defined similarly.

It is well known that k-triangulations of the n-gon can be seen as k-north-east fillings of the staircase shape (n - 1, ..., 2, 1), and furthermore, k-fans of Dyck paths of length 2(n - 2k) can be seen as k-south-east fillings of the same staircase (see e.g. [Kra06, Rub06]). Thus, the second main theorem is a clear extension of the first. It answers a questions raised by C. Krattenthaler in [Kra06].

Theorem 1.2 Let [lambda] be a Ferrers shape and let k be a positive integer. There is an explicit bijection between k-north-east and k-south-east fillings of [lambda].

The constructed bijection goes through two intermediate objects, namely through pipe dreams and flagged tableaux, both arising in the theory of Schubert polynomials. The third main theorem is a central step in the proof of Theorem 1.2 and it concerns the connection between north-east chains and reduced pipe dreams.

Theorem 1.3 Let [lambda] be a Ferrers shape and let k be a positive integer. There exists a canonical bijection between k-north-east fillings of [lambda] and reduced pipe dreams of a permutation depending on [lambda] and k.

This bijection will be described in Section 2. A variation of the argument gives the following generalization to moon polyominoes as defined in Section 2.2.

Theorem 1.4 Let M be a moon polyomino and let k be a positive integer. Then there exists a canonical bijection between k-north-east fillings of M and reduced pipe dreams (of a given permutation) living inside M.

We will use the construction to obtain new properties and simple proofs for known properties of k-northeast fillings and of k-triangulations. In particular, we obtain the following corollaries.

Corollary 1.5 The simplicial complex with facets being k-north-east fillings of a moon polyomino M is the join of a vertex-decomposable, triangulated sphere with a full simplex. In particular, it is shellable and Cohen-Macaulay.

Corollary 1.6 Let S be a stack polyomino and [lambda] the Ferrers shape obtained from S be properly rearranging its columns. Let [sigma] and [tau] be the associated permutations. Then the difference

[S.sub.[sigma]] ([x.sub.1], [x.sub.2], ...) - [S.sub.[tau]]([x.sub.1], [x.sub.2], ...)

of Schubert polynomials is monomial positive.

The bijection for k-triangulations has the additional property that the cyclic action given by rotation of the n-gon corresponds to a promotion-like operation on flagged tableaux and thus transforms a conjectured cyclic sieving phenomenon (CSP) into the context of k-flagged tableaux.

Conjecture 1.7 Let FT([lambda], k) be the set of k-flagged tableaux and let [rho] be the promotion-like cyclic action on FT([lambda], k). The triple exhibits the CSP, where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a natural q-analogue of the cardinality of [F.sub.NE] ([lambda], k).

[FIGURE 1 OMITTED]

2 From north-east fillings to pipe dreams

In this section we exhibit a connection between k-north-east fillings of Ferrers shapes as well as of stack and moon polyominoes on the one hand and reduced pipe dreams on the other. This generalizes a construction by the second author for k-triangulations [Stu10].

Reduced pipe dreams (or rc-graphs) were introduced by S. Fomin and A. Kirillov in [FK96] (see also [BB93] and [KM05, Section 1.4]). They play a central role in the combinatorics of Schubert polynomials of A. Lascoux and M.-P. Schutzenberger. A pipe dream of size n is a filling of the staircase shape (n - 1, ..., 2, 1) where each box contains two crossing pipes + or two turning pipes [??]. See Figure 1(b) for an example. A pipe dream is identified with its set of boxes containing two crossing pipes +. The permutation [pi](D) of a pipe dream D is obtained by following the pipes starting from the top and going all the way to the left, and then reading [pi](D) on the left from top to bottom in one line notation. For example, the permutation of the pipe dream in Figure 1(b) is [1, 2, 7, 6, 5, 8, 3, 4, 9, 10]. A pipe dream is reduced if two pipes cross at most once. We say that a pipe dream lives inside a set M of boxes in the staircase shape if all its crossings are contained in M. For a given permutation [pi] and a set M of boxes, denote the set of reduced pipe dreams for [pi] by RP([pi]) and the set of reduced pipe dreams for [pi] which live inside M by RP([pi], M).

2.1 A bijection between north-east fillings and reduced pipe dreams

Starting with a k-north-east filling of [lambda], one obtains a pipe dream by replacing every 1 by two turning pipes and every 0 by two crossing pipes. Afterwards, [lambda] is embedded into the smallest staircase containing it, and all boxes in the staircase outside of [lambda] are replaced by turning pipes. In other words, a k-north-east filling of [lambda] and its associated pipe dream are complementary (0,1)-fillings of [lambda] when both are identified with their sets of boxes. For example, the +'s in the pipe dream in Figure 1(b) and the marked boxes in (a) are complementary (0,1)-fillings of [lambda]. The pieces in boxes outside of [lambda] are drawn in the pipe dream in red whereas pieces within [lambda] are drawn in green. We call this identification between k-north-east fillings of [lambda] and reduced pipe dreams complementary map.

[FIGURE 2 OMITTED]

For a permutation [sigma] [member of] [S.sub.n], define its (Rothe) diagram (see [Man01, Section 2.1]) to be the set of boxes in the staircase shape given by

D([sigma]) := {(i, [[sigma].sub.j]) : i < j, [[sigma].sub.i] > [[sigma].sub.j]}.

For example, the diagram of [[sigma].sub.2]([lambda]) in Figure 2 is given by the shaded area. Clearly, the number of boxes in D([sigma]) equals the length of [sigma], i.e., the minimal number of simple transpositions needed to write [sigma]. A permutation is called dominant if its diagram is a Ferrers shape containing the box (1, 1). By construction, different permutations in [S.sub.n] have different shapes and one can obtain every Ferrers shape in this way for some n. Thus, starting with a Ferrers shape [lambda], let [sigma]([lambda]) be the unique dominant permutation [sigma] [member of] [S.sub.n] for which D([sigma]) = [lambda], where n is given by the smallest staircase shape containing [lambda]. Moreover, define [[sigma].sub.k]([lambda]) to be

[1.sub.k] x [tau] := [1, 2, ..., k, [[tau].sub.1] + k, ..., [[tau].sub.n] + k] [member of] [S.sub.n+k]

where [tau] = [sigma]([mu]) and [mu] is obtained from A by removing its first k rows and columns. Graphically, this means that [[sigma].sub.k]([lambda]) is obtained by removing the first k columns and rows from [sigma]([lambda]). Note that the northwest corner of [[sigma].sub.k]([lambda]) remains in box (k + 1, k + 1). See Figure 2 for [[sigma].sub.2]([lambda]) with [lambda] as in Figure 1. The following theorem is a more precise reformulation of Theorem 1.3.

Theorem 2.1 Let [lambda] be a Ferrers shape and let [sigma] = [[sigma].sub.k]([lambda]). The complementary map from k- north-east fillings to pipe dreams is a bijection between [F.sub.NE]([lambda], k) and RP([sigma]).

2.2 Generalizations to moon polyominoes

The results in the previous section can be partially generalized to moon polyominoes which were studied by J. Jonsson in [Jon05]. A polyomino M (i.e., a set of boxes in the positive integer quadrant) is called convex if for any two boxes in M lying in the same row or column, all boxes in between are also contained in M. Moreover, M is called intersection-free if for any two columns (or equivalently, rows) of M, one is contained in the other. A polyomino is called a moon polyomino if it is convex and intersection-free.

[FIGURE 3 OMITTED]

Without loss of generality we consider always moon polyominoes which are north-west justified, namely, they contain boxes both in the first row and in the first column. Observe that Ferrers shapes are special types of moon polyominoes. A k-filling of a moon polyomino is defined exactly in the same way as for a Ferrers shape. See Figure 3 for an example.

To connect k-north-east fillings of a moon polyomino M and pipe dreams of a certain permutation [sigma] = [[sigma].sub.k](M), we must relate maximal fillings of M which do not contain a (k + 1)-north-east chain in one of its maximal rectangles and maximal fillings of the staircase (n - 1, ..., 2, 1) which do not contain a north-east chain of length [r.sub.[sigma]] (p, q) +1 in any rectangle [p] x [q]. Define [[sigma].sub.k] (M) as follows: for a maximal rectangle R in M of width and height both strictly larger than k, let (a + 1, b + 1) and (i, j) be its northwest and south-east corner boxes. Mark the box (i + b, j + a) with a + b + k. [[sigma].sub.k] (M) is the permutation with this collection as its essential set. This means that the diagram D([sigma]) of [sigma] has (i + b, j + a) as a south-east corner with labels [r.sub.[sigma]] (i + b, j + a) = a + b + k. Using [Man01, 2.2.8], it is easy to see that this construction is well defined. Note that maximal rectangles of width or height less than or equal to k cannot contain any north-east chain of length larger than k and thus do not contribute to the essential set of the corresponding permutation. For example, the moon polyomino M in Figure 3(a) has maximal rectangles (a + 1, b + 1) - (i, j) given by

(1, 3) - (5, 5), (1, 3) - (6, 4), (3, 1) - (4, 7), (2, 2) - (5, 5), (2,1) - (4,6),

where the first maximal rectangle is highlighted. Thus, for k = 1, the resulting essential set and the associated diagram can be seen in Figure 4 and the associated permutation is [[sigma].sub.1] (M) = [1, 2, 8, 10, 3, 7, 6, 5, 4, 9]. As all maximal rectangles in a Ferrers shape are of the form [p] x [q], the definition of [[sigma].sub.k]([lambda]) reduces in this case to the definition given in the previous section.

[FIGURE 4 OMITTED]

The following theorem is a more precise reformulation of Theorem 1.4.

Theorem 2.2 The complementary map from k-north-east fillings of a moon polyomino M to pipe dreams of [sigma] = [[sigma].sub.k](M) is a bijection between [F.sub.NE](M, k) and RP([sigma], M).

We now use this theorem together with the main theorem in [Jon05] to get new insights on pipe dreams. A stack polyomino is a moon polyomino where every column starts in the first row. Let S be a stack polyomino and let [lambda] be the Ferrers shape obtained from S by properly rearranging the columns. J. Jonsson proved in [Jon05, Theorem 14] that the number of k-north-east fillings of S with a given number of +'s in every row equals the number of k-north-east fillings in [lambda] with the same number of +'s in every row. Moreover, he conjectured that this property still holds if the stack polyomino S is replaced by a moon polyomino. Therefore, we obtain the following corollary and the conjecture for the analogous statement for moon polyominoes.

Corollary 2.3 Let S be a stack polyomino and let [lambda] be the associated Ferrers shape. The number of pipe dreams in RP([[sigma].sub.k](S), S) with a given number of crossings in every row is equal to the number of pipe dreams in RP([[sigma].sub.k]([lambda])) with the same number of crossings in every row.

2.3 The simplicial complex of north-east-fillings

We are now in position to obtain Corollary 1.5. The canonical connection between k-north-east fillings and reduced pipe dreams can be used in the same way as described in the proof of [Stu10, Corollary 1.3] for k-triangulations in this more general setting. For the necessary background on simplicial complexes and in particular on subword complexes, we refer to [KM04]. A box in a moon polyomino M is called passive if it is not contained in any north-east chain in M of length k + 1. Let [DELTA](M, k) be the simplicial complex with vertices being the collection of boxes in M, and with facets being k-north-east fillings of M.

Corollary 2.4 [DELTA](M, k) is the join of a vertex-decomposable, triangulated sphere and a full simplex of dimension i - 1 , where i equals the number of passive boxes in M. In particular, it is shellable and Cohen-Macauley.

[FIGURE 5 OMITTED]

2.4 A mutation-like operation on pipe dreams

Generalizing the notion in the previous section, one can define a pure simplicial complex [DELTA]([sigma]) for any [sigma] [member of] [S.sub.n] by defining the facets as the complements in the staircase of reduced pipe dreams in RP([sigma]) (see [KM04]). Using the property that two pipes in a reduced pipe dream D cross at most once, one can define a mutation-like operation on facets of [DELTA]([sigma]) as follows. One can mutate the facet F(D) of [DELTA]([sigma]) associated to D at a vertex b if the two pipes in D which touch in b cross somewhere else. In other words, one can mutate F(D) at a vertex b if the starting points i < j of the two pipes in D which touch in b form an inversion of [sigma]. The mutation of F(D) at such a vertex b is then defined to be the facet F(D') for the reduced pipe dream D' such that

(i) the two turning pipes in b are replaced in D' by two crossing pipes,

(ii) the unique crossing b' of those two pipes is replaced in D' by two turning pipes.

By construction, the pipe dream D' = (D [union] b) \ b' is again in RP([sigma]) and thus its complement F(D') = (F(D) \ b) [union] b' forms another facet of [DELTA]([sigma]).

3 From pipe dreams to south-east fillings

In this section we describe a bijection between pipe dreams for [[sigma].sub.k]([lambda]) and k-south east fillings of [lambda], for a Ferrers shape [lambda]. For the sake of readability, we do this construction in several steps.

3.1 From pipe dreams to flagged tableaux

Define a k-flagged tableau as a semistandard tableau in which the entries in the i-th row are smaller than or equal to i + k, and denote the set of k-flagged tableaux of shape [lambda] by FT([lambda], k). These were introduced by M. Wachs [Wac85] in the study of flagged Schur functions, thus the choice of terminology. We now present a bijection between the set RP([sigma]) of reduced pipe dreams of [sigma] = [[sigma].sub.k]([lambda]) and the set FT([mu], k) of k-flagged tableaux of shape [mu] = D([sigma]).

For a reduced pipe dream D [member of] RP([sigma]) with [sigma] being of length l, define the reading biword to be the 2 x l array by reading [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every crossing box (i, j) in D row by row from east to west and from north to south. See Figure 5 for an example. It is known (and easy to check) that this gives a bijection between RP([sigma]) and the set of compatible sequences CS([sigma]), defined by S. Billey, W. Jockush and R. Stanley in [BJS93] as the set of all 2 x l arrays of the form [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] satisfying the following properties:

1. [a.sub.1] [less than or equal to] [a.sub.2] [less than or equal to] ... [less than or equal to] [a.sub.l],

2. if [a.sub.i] =[ .sub.ai+1], then [b.sub.i] > [b.sub.i+1],

3. [b.sub.1][b.sub.2] ... [b.sub.l] is a reduced word for [sigma], where i denotes the simple transposition [s.sub.i] = (i, i + 1), and

4. [a.sub.i] [less than or equal to] [b.sub.i].

One can see from the definition that a compatible sequence t for [sigma] can be written as the concatenation t = [t.sub.1] ... [t.sub.m], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [w.sub.i] is decreasing. Observe that [sigma] fixes all j [less than or equal to] k and thus, every letter in [w.sub.i] is larger than or equal to max(i, k).

Define a map CS([sigma]) [right arrow] FT([mu], k) as follows. Let t [member of]CS([sigma]) be a compatible sequence for [sigma]. Insert the letters of the word formed by the bottom row of t using column Edelman-Greene insertion [EG87] into a tableau, while recording the corresponding letters from the first row. This produces an insertion tableau P(t) and a recording tableau Q(t). The image in FT([mu], k) is now defined to be Q(t).

Theorem 3.1 Let [sigma] = [[sigma].sub.k]([lambda]) for a Ferrers shape [lambda], and let [mu] = D([sigma]). The map sending D in RP([sigma]) to the recording tableau of the reading biword of D is a bijection between RP([sigma]) and FT([mu], k).

An example of the bijection can be seen in Figure 5.

3.2 A cyclic action on flagged tableaux

In this subsection we define a cyclic action on k-flagged tableaux. The flagged promotion [rho](Q) of a k-flagged tableau Q is defined as follows.

(i) Delete all the instances of the letter 1,

(ii) apply jeu de taquin to the remaining entries,

(iii) subtract 1 from all the entries,

(iv) label each empty box on row i with i + k.

One can easily see that [rho](Q) is indeed a k-flagged tableau, since the empty boxes after step (iii) must form a horizontal strip, which means there is at most one empty box per column. Furthermore, as every box gets moved at most up by one row, and at the end one subtracts 1 from all the entries, the tableau obtained after step (iii) is k-flagged as well. The argument is finalized with the observation that if one adds a horizontal strip in which every box gets added its maximum possible value, the tableau is still k-flagged, since the row-weakness is assured by the maximality of the value of the entries on each row, and the column-strictness is assured by the fact that the entries in row i - 1 are all strictly less than the maximal value on row i.

3.3 From flagged tableaux to fans of paths and south-east fillings

We proceed as in [FK97] to obtain a reverse plane partition of height k from a k-flagged tableau. Let [lambda] be a Ferrers shape and let [mu] = D([[sigma].sub.k]([lambda])). Since every entry in row i of a k-flagged tableau of shape [mu] is less than or equal to i + k and greater than or equal to i (as the tableau is semistandard), one can subtract i from all the entries in row i, for all rows, and obtain a reverse plane partition of height k and shape [mu], or equivalently, a k-fan of noncrossing north-east paths inside To obtain a bijection between k-flagged tableaux of shape [mu] and the set [F.sub.SE]([lambda], k) of k-south-east fillings of the shape [lambda], one lifts the i-th path from the bottom by i -- 1 and turns it into a path of +'s inside [lambda]. See Figure 6 for an example; the red marks come from the red path, the blue from the blue path, and the additional black marks are contained in any 2-south-east filling.

[FIGURE 6 OMITTED]

Putting the described bijections together, we obtain Theorem 1.2.

Theorem 3.2 Let [lambda] be a Ferrers shape. The composition ofthe described maps is a bijection between [F.sub.NE]([lambda]) and [F.sub.SE]([lambda]).

As mentioned in the introduction, k-triangulations of the n-gon can be seen as k-north-east fillings of the staircase shape (n - 1, ..., 2, 1), and k-fans of Dyck paths of length 2(n - 2k) can be seen as k-southeast fillings of the same staircase (see e.g. [Kra06, Rub06]). Thus, we obtain Theorem 1.1. See Figure 7 for an example.

Corollary 3.3 In the case where A is the staircase shape (n - 1, ..., 2, 1), the described map is a bijection between k-triangulations of the n-gon and k-fans of noncrossing Dyck paths oflength 2(n - 2k).

4 Properties of north-east fillings and k-triangulations

Using Theorem 2.2, we obtain several properties of k-north-east fillings of moon polyominoes and of Ferrers shapes and k-triangulations in particular. Some of them where already known while others where only conjectured.

The first property was proved in the case of stack polyominoes by J. Jonsson in [Jon05, Theorem 10]. It follows immediately from Theorem 2.1.

Corollary 4.1 Every k-north-east filling of a moon polyomino M contains i many boxes where i equals the total number of boxes in M minus the length of [[sigma].sub.k](M). In particular i equals the number of boxes in the first k rows and columns in the case of Ferrers shapes.

The second property is part of the main theorem in [PS09, Theorem 1.4(i)] and concerns the star property as described as well in [Stu10]; for the notion used here, we refer as well to the latter.

Corollary 4.2 Every k-triangulation of the n-gon consists of exactly n - 2k k-stars.

Using the description of mutations for k-triangulations in Section 2.4, one can also describe the mutation of a facet in the simplicial complex

[[DELTA].sub.n,k] := [DELTA]([1.sub.k] x [n - 2k, ..., 1]).

[FIGURE 7 OMITTED]

This mutation corresponds to removing a diagonal in a k-triangulation and replacing it by the unique other diagonal which gives a k-triangulation. This operation is called flip in [PS09, Theorem 1.4(iii)].

Corollary 4.3 A facet F in the simplicial complex [[DELTA].sub.n,k] can be mutated at any vertex d = (i, j) [member of] F for which k < [absolute value of i - j] < n -- k.

The next property of the constructed bijection is a refined counting of k-triangulations, as conjectured by C. Nicolas [Nic09].

Theorem 4.4 The number of k-triangulations of a convex n-gon having degree d in a given vertex is given by the determinantal expression

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [Cat.sub.l] is the usual Catalan number, and where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4.1 Rotation of the n-gon and a CSP for flagged tableaux

There is a natural cyclic action [rho] on k-triangulations given by rotating the vertex labels in the n-gon counterclockwise. The following conjecture is due to V. Reiner [Rei09].

Conjecture 4.5 (V. Reiner) Let [lambda] be the staircase shape (n - 1, ..., 2, 1) and let k be a positive integer. The triple

([F.sub.NE]([lambda], k), <[rho]>, F(q))

exhibits the cyclic sieving phenomenon (CSP) as described in [RSW04].

We can describe the cyclic action on k-triangulations induced by rotation in terms of the cyclic action on flagged tableaux as defined in Section 3.2.

Theorem 4.6 The constructed bijection maps the cyclic action on k-triangulations to the cyclic action given by flagged promotion on flagged tableaux.

Using this connection, we obtain the following corollary.

Corollary 4.7 Conjecture 1.7 is equivalent to Conjecture 4.5.

5 Schubert polynomials and geometry of Schubert varieties

In this section we use the results about moon polyominoes in Section 2.2 to obtain new properties of Schubert polynomials. It was shown in [FK96] that Schubert polynomials are a generating series for pipe dreams, more precisely, for a permutation [sigma],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We obtain the following theorem and thus Corollary 1.6.

Theorem 5.1 Let S be a stack polyomino, let [lambda] be the associated Ferrers shape and let k be a positive integer. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is monomial positive. In particular, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is greater than or equal to the number of k-flagged tableaux of shape [lambda].

Let B be the subgroup of GL(n) consisting of upper triangular matrices. For each [sigma] [member of] [S.sub.n] there is a subvariety [X.sub.[sigma]] of GL(n)/B known as the Schubert variety (see, e.g., [Man01, Chapter 3]). A. Knutson and E. Miller showed in [KM05] that the multiplicity of the point [X.sub.e] at the Schubert variety [X.sub.[sigma]] is given by the specialization [G.sub.[sigma]](1, 1, ...). Thus, from the previous theorem, one obtains the following corollary.

Corollary 5.2 The multiplicity of the point [X.sub.e] at the Schubert variety [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is greater than or equal to the multiplicity of the point [X.sub.e] at the Schubert variety [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

References

[BB93] N. Bergeron and S. Billey, RC-graphs and Schubert polynomials, Experiment. Math. 2 (1993), no. 4, 257-269.

[BJS93] S. Billey, W. Jockush, and R. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), 344-374.

[EG87] P. Edelman and C. Greene, Balanced tableaux, Adv. Math. 63 (1987), no. 1, 42-99.

[Eli07] S. Elizalde, A bijection between 2-triangulations and pairs of non-crossing Dyck paths, J. Combin. Theory Ser. A 114 (2007), no. 8, 1481-1503.

[FK96] S. Fomin and A. Kirillov, The Yang-Baxter equation, symmetric functions, and Schubert polynomials, Discrete Math. 153 (1996), 123-143.

[FK97] --, Reduced words and plane partitions, J. Algebraic Combin. 6 (1997), no. 4, 311-319.

[Jon05] J. Jonsson, Generalized triangulations and diagonal-free subsets of stack polyominos, J. Comb. Theory, Ser. A 112 (2005), 117-142.

[KM04] A. Knutson and E. Miller, Subword complexes in Coxeter groups, Adv. Math. 184 (2004), no. 1, 161-176.

[KM05] --, Grobner geometry of Schubert polynomials, Ann. of Math. 161 (2005), no. 3, 1245-1318.

[Kra06] C. Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. in Appl. Math. 37 (2006), 404-431.

[Man01] L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS Texts and Monographs 6 (2001).

[Nic09] C. Nicolas, Another bijection between 2-triangulations and pairs of non-crossing Dyck paths, in DMTCS as part of the FPSAC 2009 conference proceedings (2009).

[PS09] V. Pilaud and F. Santos, Multitriangulations as complexes of star polygons, Discrete Comput. Geom. 41 (2009), no. 2, 284-317.

[Rei09] V. Reiner, personal communication.

[RSW04] V. Reiner, D. Stanton, and D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), 17-50.

[Rub06] M. Rubey, Increasing and decreasing sequences in fillings of moon polyominoes, to appear in Adv. in Appl. Math., available at arXiv:math/0 60414 0 (2006).

[Stu10] C. Stump, A new perspective on k-triangulations, J. Combin. Theory Ser. A 118 (2010), no. 6, 1794-1800.

[Wac85] M. Wachs, Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Combin. Theory Ser. A 40 (1985), no. 2, 276-289.

Luis Serrano and Christian Stump

LaCIM, University du Quebec a Montreal, Montreal, Canada
No portion of this article can be reproduced without the express written permission from the copyright holder.

Author: Printer friendly Cite/link Email Feedback Serrano, Luis; Stump, Christian DMTCS Proceedings Report 1CANA Jan 1, 2011 4799 The equivariant topology of stable Kneser graphs. A q-analog of Ljunggren's binomial congruence. Combinatorics Functional equations Functions Functions (Mathematics) Polynomials