Miles Eli Jones
email: mjones@inst-mat.utalca.cl

Luc Lapointe
email: lapointe@inst-mat.utalca.cl

Pieri rules for Schur functions in superspace

Keywords: Schur functions, Key polynomials, symmetric functions in superspace

The Schur functions in superspace sΛ and sΛ are the limits q = t = 0 and q = t = ∞ respectively of the Macdonald polynomials in superspace. We present the elementary properties of the bases sΛ and sΛ (which happen to be essentially dual) such as Pieri rules, dualities, monomial expansions, tableaux generating functions, and Cauchy identities.

Résumé. Les fonctions de Schur dans le superespace sΛ et sΛ sont les limites q = t = 0 et q = t = ∞ respectivement des polynômes de Macdonald dans le superespace. Nous présentons les propriétés élémentaires des bases sΛ et sΛ (qui sont essentiellement duales l'une de l'autre) tels que les règles de Pieri, la dualité, le développement en fonctions monomiales, les fonctions génératrices de tableaux et les identités de Cauchy.

Introduction

An extension to superspace of the theory of symmetric functions was developed in [START_REF] Blondeau-Fournier | Macdonald polynomials in superspace as eigenfunctions of commuting operators[END_REF][START_REF] Desrosiers | Classical symmetric functions in superspace[END_REF][START_REF] Desrosiers | Orthogonality of Jack polynomials in superspace[END_REF]. In this extension, the polynomials f (x, θ), where (x, θ) = (x 1 , . . . , x N , θ 1 , . . . , θ N ), not only depend on the usual commuting variables x 1 , . . . , x N but also on the anticommuting variables θ 1 , . . . , θ N (θ i θ j = -θ j θ i , and θ 2 i = 0). In this extended abstract, we are concerned with two natural generalizations to superspace of the Schur functions that arise as special limits of the Macdonald polynomials in superspace and whose combinatorics appears to be extremely rich.

The extension to superspace of the Macdonald polynomials, {P Λ (x, θ; q, t)} Λ , is a basis of the ring Q(q, t)[x 1 , . . . , x N ; θ 1 , . . . , θ N ] S N of symmetric polynomials in superspace, where the superscript S N indicates that the elements of the ring are invariant under the diagonal action of the symmetric group S N (that is, invariant under the simultaneous interchange of x i ↔ x j and θ i ↔ θ j , for any i, j). They are indexed by superpartitions Λ and defined as the unique basis such that 1. P Λ (q, t) = m Λ + smaller terms 2. P Λ (q, t), P Ω (q, t) q,t = 0 if Λ = Ω where the scalar product •, • q,t is given by

p Λ , p Ω q,t = δ ΛΩ q |Λ a | z Λ s i 1 -q Λ s i 1 -t Λ s i (1)
on the power sum symmetric functions in superspace (see Section 2 for all the relevant definitions). It was shown in [START_REF] Blondeau-Fournier | Macdonald polynomials in superspace as eigenfunctions of commuting operators[END_REF] that even though the limits q = t = 0 and q = t = ∞ of this scalar product are degenerate and not well-defined respectively, the corresponding limits s Λ := P Λ (0, 0) and sΛ := P Λ (∞, ∞) of the Macdonald superpolynomials exist and are related to Key polynomials [START_REF] Ion | Demazure characters and non-symmetric Macdonald polynomials[END_REF][START_REF] Lascoux | Keys and standard bases, Invariant Theory and Tableaux[END_REF]. As we will see, the rich combinatorics of these functions makes them the genuine extensions to superspace of the Schur functions. In comparison, the a priori more relevant limit q = t = 1 of the Macdonald polynomials in superspace, which corresponds to the limit α = 1 of the Jack polynomials in superspace, does not seem to be very interesting from the combinatorial point of view.

The basis s Λ is especially relevant since it plays the role of the Schur functions in the generalization to superspace of the original Macdonald positivity conjectures [START_REF] Blondeau-Fournier | Macdonald polynomials in superspace: conjectural definition and positivity conjectures[END_REF]. To be more specific, let J Λ (q, t) = c Λ (q, t)P Λ (q, t) be the integral form of the Macdonald superpolynomials (c Λ (q, t) is a constant belonging to Z[q, t]) and let ψ(s Λ ) be a certain plethystically transformed version of the function s Λ (see [START_REF] Blondeau-Fournier | Macdonald polynomials in superspace: conjectural definition and positivity conjectures[END_REF] for more details). Then the coefficients K ΩΛ (q, t) appearing in

J Λ (q, t) = Ω K ΩΛ (q, t) ψ(s Ω ) (2)
are conjectured to be polynomials in q and t with nonnegative integer coefficients (the conjecture is known to hold when the degree in the anticommuting variables is either zero, which corresponds to the usual Macdonald case, or sufficiently large [START_REF] Blondeau-Fournier | Double Macdonald polynomials as the stable limit of Macdonald superpolynomials[END_REF]).

In this extended abstract we will present the elementary properties of the bases s Λ and sΛ (which as we will see are essentially dual) such as Pieri rules, dualities, monomial expansions, tableaux generating functions, and Cauchy identities. It is important to note that the combinatorics of the bases s Λ and sΛ was first studied in [START_REF] Blondeau-Fournier | Schur superpolynomials: combinatorial definition and Pieri rule[END_REF]. Our work stems in large part from a desire to develop the right framework to prove the conjectures therein, especially those concerning Pieri rules and tableaux generating functions.

We are confident that this work is only the tip of the iceberg and that deeper properties of the bases s Λ and sΛ will be uncovered in the future, such as for instance a group-theoretical interpretation of the generalization to superspace of the Macdonald positivity conjecture. At the tableau level, we are hopeful that this work will eventually lead to a Robinson-Schensted-Knuth insertion algorithm in superspace, and ultimately to a charge statistic on tableaux that would solve the case q = 0 of (2).

The most technical parts of this work, which are not included in this extended abstract, are the proofs of the Pieri rules [9]. They rely on the correspondence between the Schur functions in superspace and Key polynomials [START_REF] Blondeau-Fournier | Macdonald polynomials in superspace as eigenfunctions of commuting operators[END_REF] that allows to use the powerful machinery of divided differences [START_REF] Lascoux | Symmetric functions and combinatorial operators on polynomials[END_REF]. Once the Pieri rules are assumed to hold, the remaining results follow somewhat easily from duality arguments or well-known techniques of symmetric function theory [9,[START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF][START_REF] Stanley | Enumerative Combinatorics[END_REF].

2 Symmetric function theory in superspace: basic definitions A polynomial in superspace, or equivalently, a superpolynomial, is a polynomial in the usual N variables x 1 , . . . , x N and the N anticommuting variables θ 1 , . . . , θ N over a certain field, which will be taken in the remainder of this article to be Q. A superpolynomial P (x, θ), with x = (x 1 , . . . , x N ) and θ = (θ 1 , . . . , θ N ), is said to be symmetric if the following is satisfied:

P (x 1 , . . . , x N , θ 1 , . . . , θ N ) = P (x σ(1) , . . . , x σ(N ) , θ σ(1) , . . . , θ σ(N ) ) ∀ σ ∈ S N (3)
where S N is the symmetric group on {1, . . . , N }.

Superpartitions

Before defining superpartitions, we recall some definitions related to partitions [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. A partition λ = (λ Symmetric superpolynomials are naturally indexed by superpartitions (i) . A superpartition Λ of degree (n|m) is a pair (Λ , Λ * ) of partitions Λ and Λ * such that:

1. Λ * ⊆ Λ ; 2. the degree of Λ * is n; 3. the skew diagram Λ /Λ * is both a horizontal and a vertical m-strip (ii) We refer to m and n respectively as the fermionic degree and total degree of Λ. Obviously, if Λ = Λ * = λ, then Λ = (λ, λ) can be interpreted as the partition λ.

We will also need another characterization of a superpartition. A superpartition Λ is a pair of partitions (Λ a ; Λ s ) = (Λ 1 , . . . , Λ m ; Λ m+1 , . . . , Λ N ), where Λ a is a partition with m distinct parts (one of them possibly equal to zero), and Λ s is an ordinary partition (with possibly a string of zeros at the end). The correspondence between (Λ , Λ * ) and (Λ a ; Λ s ) is given explicitly as follows: given (Λ , Λ * ), the parts of Λ a correspond to the parts of Λ * such that Λ i = Λ * i , while the parts of Λ s correspond to the parts of Λ * such that Λ

i = Λ * i . The conjugate of a superpartition Λ = (Λ , Λ * ) is Λ = ((Λ ) , (Λ * ) ). A diagrammatic representation of Λ is given by the Ferrers diagram of Λ * with circles added in the cells corre- sponding to Λ /Λ * . For instance, if Λ = (Λ a ; Λ s ) = (3, 1, 0; 2, 1), we have Λ = (4, 2, 2, 1, 1) and Λ * = (3, 2, 1, 1), so that e e e Λ : e e e , (4)
(i) Superpartitions correspond, after a trivial bijection, to the overpartitions studied in [START_REF] Corteel | Overpartitions[END_REF].

(ii) Such diagrams are sometimes called m-rook strips.

where the last diagram illustrates the conjugation operation that corresponds, as usual, to replacing rows by columns.

The extension of the dominance ordering to superpartitions is

Ω ≤ Λ iff deg(Λ) = deg(Ω), Ω * ≤ Λ * and Ω ≤ Λ ( 5
)
where the order on partitions is the usual dominance ordering

µ ≤ λ iff |µ| = |λ| and µ 1 + • • • + µ i ≤ λ 1 + • • • + λ i ∀i . (6)

Simple bases

Four simple bases of the space of symmetric polynomials in superspace will be particularly relevant to our work [START_REF] Desrosiers | Classical symmetric functions in superspace[END_REF]:

1. the extension of the monomial symmetric functions, m Λ , defined by

m Λ = σ∈S N θ σ(1) • • • θ σ(m) x Λ1 σ(1) • • • x Λ N σ(N ) , (7)
where the sum is over the permutations of {1, . . . , N } that produce distinct terms, and where the entries of (Λ 1 , . . . , Λ N ) are those of Λ = (Λ a ; Λ s ) = (Λ 1 , . . . , Λ m ; Λ m+1 , . . . , Λ N ) (the semicolon is removed);

2. the generalization of the power-sum symmetric functions

p Λ = pΛ1 • • • pΛm p Λm+1 • • • p Λ , where pk = N i=1 θ i x k i and p r = N i=1 x r i , for k ≥ 0, r ≥ 1; (8)
3. the generalization of the elementary symmetric functions e Λ = ẽΛ1

• • • ẽΛm e Λm+1 • • • e Λ ,
where ẽk = m (0;1 k ) and e r = m (∅;1 r ) , for k ≥ 0, r ≥ 1; (9)

the generalization of the homogeneous symmetric functions h

Λ = hΛ1 • • • hΛm h Λm+1 • • • h Λ , where hk = deg(Λ s )=k deg(Λ a )=1 (Λ 1 + 1)m Λ and h r = deg(Λ s )=r deg(Λ a )=0 m Λ , for k ≥ 0, r ≥ 1 ( 10
)
Observe that when Λ = (∅; λ), we have that m Λ = m λ , p Λ = p λ , e Λ = e λ and h Λ = h λ are respectively the usual monomial, power-sum, elementary and homogeneous symmetric functions. Also note that if we define the operator

d = θ 1 ∂/∂x 1 + • • • + θ N ∂/∂x N , we have (k + 1) pk = d(p k+1 ) , ẽk = d(e k+1 ) and hk = d(h k+1 ) (11)
that is, the new generators in the superspace versions of the bases can be obtained from acting with d on the generators of the usual symmetric function versions.

Scalar product and duality

The relevant scalar product in this article is the specialization q = t = 1 of the scalar product (1) (iii) , that is,

p Λ , p Ω = δ ΛΩ z Λ s (12)
where, as usual,

z λ = 1 n λ (1) n λ (1)! 2 n λ (2) n λ (2)! • • • with n λ (i) the number of parts of λ equal to i. This scalar product is such that h Λ , m Ω = δ ΛΩ (13)
The homomorphism ω defined by

ω(p r ) = (-1) r pr and ω(p r ) = (-1) r-1 p r (14)
which is obviously an involution and an isometry of the scalar product •, • , is also such that

ω(h Λ ) = e Λ (15)
The Schur functions in superspace s Λ and sΛ were defined in the introduction as the special limits q = t = 0 and q = t = ∞ respectively of the Macdonald polynomials in superspace. Remarkably, the functions s Λ and sΛ are essentially dual with respect to our scalar product [START_REF] Blondeau-Fournier | Macdonald polynomials in superspace as eigenfunctions of commuting operators[END_REF].

Proposition 1 Let s *

Λ and s * Λ be the bases dual to the bases s Λ and sΛ respectively, that is, let s * Λ and s * Λ be such that

s * Λ , s Ω = s * Λ , sΩ = δ ΛΩ (16)
Then s * Λ = (-1) ( m 2 ) ωs Λ and s * Λ = (-1) ( m 2 ) ωs Λ ( 17
)
where m is the fermionic degree of Λ.

When m = 0, we have s Λ = s (∅;λ) = s λ and sΛ = s(∅;λ) = s λ . In this case the proposition is simply stating that the dual of the Schur function basis s λ with respect to the Hall scalar product is the basis s λ = ωs λ , which is an elementary result [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF].

Pieri rules

Pieri rules for the multiplication of a Schur functions in superspace s Λ or sΛ by e and ẽ were established in [9] using Key polynomials. By Proposition 1 and (15), these Pieri rules are the transposed of those corresponding to the multiplication of s * Λ or s * Λ by h and h which will be presented in this section.

Pieri rules for s *

Λ

Theorem 2 Let Λ be a superpartition of fermionic degree m. Then, for k ≥ 1 and ≥ 0, we have

s * Λ h k = Ω s * Ω and s * Λ h = Ω (-1) #(Ω,Λ) s * Ω ( 18
)
where the sum is over all superpartitions Ω of fermionic degree m (h k case) or m + 1 ( h case) such that (iii) The scalar product (1) differs from that of [START_REF] Blondeau-Fournier | Macdonald polynomials in superspace as eigenfunctions of commuting operators[END_REF] by a sign depending on the fermionic degree.

1. Ω * /Λ * is a horizontal k-strip (h k case) or Ω /Λ is a horizontal -strip ( h case).

2. There exists in the h case a (unique) circle of Ω (the new circle), let's say in column c, such that

• column c does not contain any cell of Ω * /Λ * .

• there is a cell of Ω * /Λ * in every column strictly to the left of column c.

3.

If Ω is Ω without its new circle ( Ω = Ω when there is no new circle), then the i-th circle (starting from below) of Ω is either in the same row as the i-th circle of Λ (if Ω * /Λ * does not contain a cell in that row) or one row below that of the i-th circle of Λ (if Ω * /Λ * contains a cell in the row of the i-th circle of Λ). In the latter case, we say that the circle was moved.

and where #(Ω, Λ) is the number of circles in Ω below the new circle.

We illustrate the rules by giving the expansions of s * (4,1,0;2) h 3 and s * (4,1;3) h3 . To generate all Ω described in Theorem 2, draw all possible horizontal strips on Λ * . For each partition obtained this way, start from the bottom row and proceed row by row. If a new square occupies the place of a circle in Λ , move the circle to the next row and slide it to the first available column. If there already is a circle occupying the row then the resulting diagram is not a superpartition and should be discarded. Note that this happens twice in our example. This rule is very similar to the previous one but in this case but keep in mind that every column to the left of the new circle must have a new box. Also, multiply by (-1) for every circle below the new circle.

Pieri rules for s *

Λ Theorem 3 Let Λ be a superpartition of fermionic degree m. Then, for k ≥ 1 and ≥ 0, we have s *

Λ h k = Ω s * Ω and s * Λ h = Ω (-1) #(Ω,Λ) s * Ω ( 19
)
where the sum is over all superpartitions Ω of fermionic degree m (h k case) or m + 1 ( h case) such that

• Ω * /Λ * is a horizontal k-strip (h k case) or Ω /Λ is a horizontal ( + 1)-strip whose rightmost cell (the new circle) belongs to Ω /Ω * ( h case).

• the i-th circles (starting from the new circle and going down, or from the first row and going down if there is no new circle) of Ω and Λ are either in the same row or the same column. In the case where the i-th circles are in the same row r, the circle in column r of Ω cannot be located passed row r -1 of Λ (if r = 1 the condition does not apply).

and where #(Ω, Λ) is again the number of circles in Ω below the new circle. To generate these superpartitions, start with the previous rule and replace the new box that is farthest to the right with the new circle. Discard any diagrams that have two circles in the same row or column.

Kostka coefficients in superspace

Define the Kostka coefficients in superspace K ΩΛ and KΩΛ to be respectively such that

h Λ = Ω K ΩΛ s * Ω and h Λ = Ω KΩΛ s * Ω ( 20
)
As expected, the Kostka coefficients in superspace give the monomial expansion of the Schur functions in superspace.

Proposition 4

We have

s Λ = Ω≤Λ KΛΩ m Ω and sΛ = Ω≤Λ K ΛΩ m Ω (21)
The triangularity in the previous equation follows from the fact that the Schur functions in superspace are special cases of Macdonald polynomials in superspace, which are triangular by construction. The Kostka coefficients in superspace turn out to be nonnegative integers, which is relatively surprising given that signs show up in the Pieri rules.

Proposition 5 The Kostka coefficients in superspace K ΩΛ and KΩΛ are nonnegative integers.

A combinatorial interpretation in terms of tableaux for the coefficients KΛΩ and K ΛΩ will be given in Proposition 8 and Proposition 9 respectively. We should note that a somewhat different combinatorial interpretation for KΛΩ and K ΛΩ was conjectured in [START_REF] Blondeau-Fournier | Schur superpolynomials: combinatorial definition and Pieri rule[END_REF].

Duality

We will now see that there is a natural duality that relates s Λ and s Λ . Unexpectedly, for reasons we will see later on, no such simple duality exists in the case of sΛ .

Applying ω on the first formula of (20), we obtain from (15) and Proposition 1 that

e Λ = (-1) ( m 2 ) Ω K ΩΛ s Ω (22)
Now, let H Λ = pΛ a h Λ s , that is, H Λ is h Λ with the superspace generators hr replaced by pr . It is shown in [9] that

H Λ = Ω K ΩΛ s Ω (23)
where we stress that the coefficients K ΩΛ are exactly those that appear in the previous equation. This suggests a natural duality between the H Λ and e Λ bases. In effect, let ϕ be the homomorphism defined by ϕ(p r ) = ẽr and ϕ(h

r ) = e r (24)
that is, such that ϕ(H Λ ) = e Λ . By ( 22) and (23), the following result is essentially immediate:

Corollary 6 We have ϕ(s Λ ) = (-1) ( m 2 ) s Λ (25)
Moreover, the homomorphism ϕ is an involution, that is, ϕ • ϕ is the identity.

Using Corollary 6, the Pieri rules for the multiplication of s Λ by p and h are identical to those for the multiplication of s * Λ by h and h respectively. We should note that these Pieri rules were conjectured to hold in [START_REF] Blondeau-Fournier | Schur superpolynomials: combinatorial definition and Pieri rule[END_REF].

Corollary 7

We have, for k ≥ 1 and ≥ 0,

s Λ h k = Ω s Ω and s Λ p = Ω (-1) #(Ω,Λ) s Ω ( 26
)
where #(Ω, Λ) is as usual the number of circles of Ω below the new circle and where the sums run over superpartitions Ω obeying the conditions of Theorem 3.

It is immediate from Proposition 1 that the linear map ω • ϕ + • ω sends sΛ to sΛ (up to a sign), where ϕ + is the adjoint of ϕ with respect to the scalar product [START_REF] Macdonald | Symmetric functions and Hall polynomials[END_REF]. But ϕ + turns out not to be a homomorphism, and as such the duality between sΛ and sΛ is less natural (for instance, it does not lead to any analog of Corollary 7).

Tableaux

In this section, we show that the Schur functions in superspace are generating series of certain types of tableaux.

We will refer to { 0, 1, 2, 3, . . . } as the set of fermionic nonnegative integers. In this spirit, we will also refer to the set of nonnegative integers {0, 1, 2, 3, . . . } as the set of bosonic nonnegative integers. For α ∈ {0, 0, 1, 1, 2, 2, . . . }, we will say that type(α) is bosonic or fermionic depending on whether the corresponding integer is fermionic or bosonic. Finally, define

|α| = a if α = ā is fermionic a if α = a is bosonic (27)

s-tableaux

By (20), the tableaux needed to represent the Schur function in superspace s Λ are those stemming from the Pieri rules associated to the multiplication of s * Λ by h r or hr given in Theorem 2. We say that the sequence Ω = Λ (0) , Λ (1) , . . . , Λ (n) = Λ is an s-tableau of shape Λ/Ω and weight (α 1 , . . . , α n ), where α i ∈ {0, 0, 1, 1, 2, 2, . . . }, if Ω = Λ (i) and Λ = Λ (i-1) obey the conditions of Theorem 2 with k = α i whenever α i is bosonic or with = |α i | whenever α i is fermionic. An s-tableau can be represented by a diagram constructed recursively in the following way:

1. the cells of Λ * (i) /Λ * (i-1) , which form a horizontal strip, are filled with the letter i. In the fermionic case, the new circle is also filled with a letter i.

2. the circles of Λ (i-1) that are moved a row below keep their fillings.

The sign of an s-tableau T , which corresponds to the product of the signs appearing in the fermionic horizontal strips, can be extracted quite efficiently from an s-tableau. Read the fillings of the circles from top to bottom to obtain a word (without repetition): the sign of the tableau T is then equal to (-1) inv(T ) , where inv(T ) is the number of inversions of the word.

Given a diagram of an s-tableau, we define the path of a given circle (filled let's say with letter i) in the following way. Let c be the leftmost column that does not contain a square (a cell of Ω * ) filled with an i. The path starts in the position of the smallest entry larger than i (let's say j) in column c. The path then moves to the smallest entry (let's say k) larger than j in the row below (if there are many such k's the path goes through the leftmost such k). We continue this way until we reach the row below that of the circle filled with an i.

It is important to realize that a tableau can be identified with its diagram given that the sequence Ω = Λ (0) , Λ (1) , . . . , Λ (n) = Λ can be recovered from the diagram. We obtain the diagram corresponding to Ω = Λ (0) , Λ (1) , . . . , Λ (n-1) by removing the letters n from the diagram (including, possibly, the circled one), and by moving the remaining circle one row above according to the following rule. A circle (filled let's say with letter i) in a given row r is moved to row r -1 if there is an n in row r -1 that belongs to its path. Otherwise the circle in row r stays in its position.

As is the case for s-tableaux, the sign of an s-tableau T is equal to (-1) inv(T ) , where inv(T ) is the number of inversions of the word obtained by reading the filling of the circles from top to bottom.

It is important to realize that the sequence Ω = Λ (0) , Λ (1) , . . . , Λ (n) = Λ can be recovered from the diagram. We obtain the diagram corresponding to Ω = Λ (0) , Λ (1) , . . . , Λ (n-1) by removing the letters n from the diagram (including, possibly, the circled one), and by moving the circled letters one cell above if there is a letter n above them or to their left if there are letters n to their left and none above them. For instance, if one considers the s-tableau T below, the sequence of superpartitions associated to it can then be recovered by stripping successively the tableaux of their largest letter: where the sum is over all s-tableaux of shape Λ. Hence, from (21), K ΛΩ = T (-1) inv(T ) , where the sum is over all s-tableaux T of shape Λ and weight ( Ω1 , . . . , Ωm , Ω m+1 , . . . , Ω N ) (recall that Ω = (Ω 1 , . . . , Ω m ; Ω m+1 , . . . , Ω N )).

The monomial expansion of s(2,0;3) is thus obtained by listing every filling of the shape (2, 0; 3) whose weight is that of a superpartition

Cauchy formulas

As is the case in symmetric function theory, the dualities of Proposition 1 translate into Cauchy type formulas. The one most relevant to this work is the following: i,j

(1 + x i y j + θ i φ j ) = Λ s Λ (x, θ) sΛ (y, φ)

where the variables y 1 , y 2 , . . . are ordinary variables while the variables φ 1 , φ 2 , . . . are anticommuting. The tableaux generating series of Propositions 8 and 9 suggest that there should exist a bijective proof of that formula using an extension to superspace of the dual Robinson-Schensted-Knuth algorithm [START_REF] Stanley | Enumerative Combinatorics[END_REF].

3 )

 3 h3 = s * (3,1,0;7) + s * (4,1,0;6) -s * (3,2,1;5) -s * (4,2,1;4) -s * (4,3,1;3)

Proposition 9

 9 We havesΛ = T (-1) inv(T ) (xθ) T(30)

  0;3) = 3 m (1,0;1,1,1,1) + 2 m (1,0;2,1,1) + m (1,0;2,2) + m (1,0;3,1) + m (2,0;1,1,1) + m (2,0;2,1) + m (2,0;3)

  1 , λ 2 , . . . ) of degree |λ| is a vector of non-negative integers such that λ i ≥ λ i+1 for i = 1, 2, . . . and such that i λ i = |λ|. Each partition λ has an associated Ferrers diagram with λ i lattice squares in the i th row, from the top to bottom. Any lattice square in the Ferrers diagram is called a cell (or simply a square), where the cell (i, j) is in the ith row and jth column of the diagram. The conjugate λ of a partition λ is represented by the diagram obtained by reflecting λ about the main diagonal. We say that the diagram µ is contained in λ, denoted µ ⊆ λ, if µ i ≤ λ i for all i. Finally, λ/µ is a horizontal (resp. vertical) n-strip if µ ⊆ λ, |λ| -|µ| = n, and the skew diagram λ/µ does not have two cells in the same column (resp. row).

  Notice here that the circle can be pushed down if there is room or pushed to the right. It cannot be pushed to the right farther than the original row above it.

	e		e
	e	+	e
	s * (4,1;5,4) h 3 = s * (4,1;8,4) + s * (4,1;7,5) + s * (4,2;7,4) + s * (4,1;7,4,1) + s * (4,2;6,5) + s * (4,1;6,5,1)
	+ s * (4,3;6,4) + s * (4,2;6,4,1) + s * (4,1;6,4,2) + s * (4,3;5,5) + s * (4,3;5,4,1) + s * (4,1;5,4,3)
			e
			e • e
	s * (4,1;5,4) h3 = s * (7,4,1;4) + s * (6,4,1;5) + s * (6,4,2;4) + s * (6,4,1;4,1) + s * (5,4,2;5) + s * (5,4,1;5,1)
	+ s * (5,4,3;4) + s * (5,4,2;4,1) + s * (5,4,1;4,2) -s * (4,2,1;5,4)

& & & &

Acknowledgements

The authors would like to thank O. Blondeau-Fournier, P. Desrosiers and P. Mathieu for very fruitful discussions. This work was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Tecnológico de Chile) postdoctoral grant #3130631 and regular grant #1130696.

Consider the tableau

The sequence of superpartitions associated to that s-tableau can then be recovered by stripping successively the tableau of its largest letter:

if T is of weight (α 1 , . . . , α n ). We stress that the product over anticommuting variables is ordered from left to right over increasing indices. For instance, for the s-tableau above, we have

where the sum is over all s-tableaux T of shape Λ. Hence, from (21), KΛΩ = T (-1) inv(T ) , where the sum is over all s-tableaux T of shape Λ and weight ( Ω1 , . . . , Ωm , Ω m+1 , . . . , Ω N ) (recall that Ω = (Ω 1 , . . . , Ω m ; Ω m+1 , . . . , Ω N )).

We thus obtain the monomial expansion of s (3,1;2,1,1) by listing every filling of the shape (3, 1; 2, 1, 1) whose weight corresponds to a superpartition:

Therefore, s (3,1;2,1,1) = 3 m (3,1;1,1,1,1) + m (3,1;2,1,1) .

s-tableaux

By (20), the tableaux needed to represent the Schur function in superspace sΛ are this time those stemming from the Pieri rules associated to the multiplication of s * Λ by h r or hr given in Theorem 3. We say that the sequence Ω = Λ (0) , Λ (1) , . . . , Λ (n) = Λ is an s-tableau of shape Λ/Ω and weight (α 1 , . . . , α n ), where α i ∈ {0, 0, 1, 1, 2, 2, . . . }, if Ω = Λ (i) and Λ = Λ (i-1) obey the conditions of Theorem 3 with k = α i whenever α i is bosonic or with = |α i | whenever α i is fermionic. An s-tableau can be represented by a diagram constructed recursively in the following way:

1. the cells of Λ * (i) /Λ * (i-1) are filled with the letter i. In the fermionic case, the new circle is also filled with a letter i 2. the circles of Λ (i-1) that moved along a column or a row keep their fillings.


Cesar Ceballos

Arnau Padrol

Camilo Sarmiento

Dyck path triangulations and extendability (extended abstract † )

Keywords: triangulations, products of simplices, Dyck paths, tropical oriented matroids

We introduce the Dyck path triangulation of the cartesian product of two simplices ∆n-1 × ∆n-1. The maximal simplices of this triangulation are given by Dyck paths, and its construction naturally generalizes to produce triangulations of ∆rn-1 × ∆n-1 using rational Dyck paths. Our study of the Dyck path triangulation is motivated by extendability problems of partial triangulations of products of two simplices. We show that whenever m ≥ k > n, any triangulation of

m-1 × ∆n-1 extends to a unique triangulation of ∆m-1 × ∆n-1. Moreover, with an explicit construction, we prove that the bound k > n is optimal. We also exhibit interpretations of our results in the language of tropical oriented matroids, which are analogous to classical results in oriented matroid theory.

Résumé. Nous introduisons la triangulation par chemins de Dyck du produit cartésien de deux simplexes ∆n-1 × ∆n-1. Les simplexes maximaux de cette triangulation sont donnés par des chemins de Dyck, et cette construction se généralise de fac ¸on naturelle pour produire des triangulations de ∆rn-1 × ∆n-1 qui utilisent des chemins de Dyck rationnels. Notre étude de la triangulation par chemins de Dyck est motivée par des problèmes de prolongement de triangulations partielles de produits de deux simplexes. On montre que si m ≥ k > n alors toute triangulation de ∆ (k-1) m-1 × ∆n-1 se prolonge en une unique triangulation de ∆m-1 × ∆n-1. De plus, avec une construction explicite, nous montrons que la borne k > n est optimale. Nous présentons aussi des interprétations de nos résultats dans le langage des matroïdes orientés tropicaux, qui sont analogues aux résultats classiques de la théorie des matroïdes orientés.

Introduction

The cartesian product of a standard (m -1)-simplex with a standard (n -1)-simplex is the (m + n -2)dimensional polytope ∆ m-1 × ∆ n-1 := conv{(e i , e j ) : e i ∈ ∆ m-1 , e j ∈ ∆ n-1 } ⊂ R m+n , where e i and e j range over the standard basis vectors of R m and R n , respectively.

Triangulations of the product of two simplices are intricate objects that have been extensively studied with various purposes. They are a key ingredient for understanding triangulations of products of polytopes [START_REF] De Loera | Nonregular triangulations of products of simplices[END_REF][START_REF] Haiman | A simple and relatively efficient triangulation of the n-cube[END_REF][START_REF] Orden | Asymptotically efficient triangulations of the d-cube[END_REF][START_REF] Santos | A point set whose space of triangulations is disconnected[END_REF]. Via the Cayley trick, they are in bijection with fine mixed subdivisions of a dilated simplex m∆ n-1 [START_REF] Santos | The Cayley trick and triangulations of products of simplices. Integer Points in Polyhedra -Geometry[END_REF], which provides a relation to tropical (pseudo) hyperplane arrangements and tropical oriented matroids [START_REF] Ardila | Tropical hyperplane arrangements and oriented matroids[END_REF][START_REF] Develin | Tropical convexity[END_REF]. Moreover, they have also attracted interest in algebraic geometry and commutative algebra [START_REF] Babson | The geometry of products of minors[END_REF][START_REF] Conca | Nice Initial Complexes of Some Classical Ideals. Algebraic and geometric combinatorics[END_REF][START_REF] Gelfand | Discriminants, resultants, and multidimensional determinants[END_REF][START_REF] Sturmfels | Gröbner bases and convex polytopes[END_REF] and in Schubert calculus [START_REF] Ardila | Flag arrangements and triangulations of products of simplices[END_REF].

In this paper, we present an intriguing family of triangulations of ∆ n-1 × ∆ n-1 that we call Dyck path triangulations, whose maximal simplices are described in terms of Dyck paths in a n × n grid under a cyclic action. The maximal simplices of the Dyck path triangulation of ∆ 2 × ∆ 2 and the corresponding fine mixed subdivision of 3∆ 2 are illustrated in Figure 1. Besides the combinatorial beauty of these triangulations, they are motivated by extendability problems of partial triangulations of ∆ m-1 × ∆ n-1 . The (k -1)-skeleton of ∆ m-1 , which we denote by ∆ (k-1) m-1 , is the polyhedral complex of all faces of ∆ m-1 of dimension less than or equal to k -1. A partial triangulation of ∆ m-1 × ∆ n-1 is a triangulation of the polyhedral complex ∆ (k-1) m-1 × ∆ n-1 . Such a triangulation is said to be extendable if it is equal to the restriction of a triangulation of ∆ m-1 × ∆ n-1 to ∆ (k-1) m-1 ×∆ n-1 . The smallest example of a non-extendable partial triangulation is shown in Figure 2(a); a more interesting example due to Santos [START_REF] Santos | Some acyclic systems of permutations are not realizable by triangulations of a product of simplices. Algebraic and Combinatorial Aspects of Tropical Geometry[END_REF] is shown in Figure 2(b).

The question of extendability of triangulations of ∆ m-1 × ∆ n-1 . Shortly after, however, the Acyclic System Conjecture was disproved by Santos [START_REF] Santos | Some acyclic systems of permutations are not realizable by triangulations of a product of simplices. Algebraic and Combinatorial Aspects of Tropical Geometry[END_REF]. These results motivate the search for necessary and sufficient conditions for extendability.

Our first contribution is the following extendability theorem.

(a) A non-extendable triangulation of

∆ (1) 2 × ∆ 1 . (b) A non-extendable triangulation of ∆ (2) 3 × ∆ 2 (Santos).
Fig. 2: Two examples of non-extendable partial triangulations. The triangulation in part (b), due to Francisco Santos [START_REF] Santos | Some acyclic systems of permutations are not realizable by triangulations of a product of simplices. Algebraic and Combinatorial Aspects of Tropical Geometry[END_REF], is shown as a subdivision of (3∆3

) (2) = ∂ (3∆3).
Theorem (Theorem 4.2). Let m, n, k be positive integers such that m ≥ k > n. Every triangulation of ∆

(k-1) m-1 × ∆ n-1 extends to a unique triangulation of ∆ m-1 × ∆ n-1 .
In considering whether the bound k > n in Theorem 4.2 is optimal, we are led to the Dyck path triangulation of ∆ n-1 ×∆ n-1 . This triangulation is our main tool to explicitly construct a family of partial triangulations that shows that the assertion of Theorem 4.2 does not generally hold when m > k = n.

Theorem (Theorem 4.3). For every n ≥ 2 there is a non-extendable triangulation of

∂ (∆ n ) × ∆ n-1 .
As suggested by its name, the Dyck path triangulation is based on Dyck paths and is related to Catalan combinatorics. We devote the rest of the paper to the study of this triangulation and its relatives. In particular, we present a natural generalization in terms of rational Dyck paths in the "Fuss-Catalan" case (rn, n). It would be interesting to know if it can be further generalized to other families of rational Dyck paths.

Via the Cayley trick [START_REF] Santos | The Cayley trick and triangulations of products of simplices. Integer Points in Polyhedra -Geometry[END_REF], Theorems 4.2 and 4.3 transform into statements about the extendability of "partial fine mixed subdivisions" of (n∆ m-1 ) (k-1) , coming from triangulations of ∆ (k-1) m-1 × ∆ n-1 , which we refer to as authentic subdivisions.

Corollary 1.1. For m ≥ k > n, every authentic subdivision of (n∆ m-1 ) (k-1) can be extended to a unique fine mixed subdivision of n∆ m-1 . Moreover, for every n ≥ 2 there is a non-extendable authentic subdivision of ∂ (n∆ n ).

Apart from providing a characterization of extendable of triangulations of ∆ (k-1) m-1 × ∆ n-1 , our results admit additional interpretations that render them of broader interest.

On the one hand, Theorems 4.2 and 4.3 naturally translate into the language of tropical oriented matroids (which we abbreviate as TOMs). This concept was introduced by Ardila and Develin as an analogue of classical oriented matroids for the tropical semiring [START_REF] Ardila | Tropical hyperplane arrangements and oriented matroids[END_REF]. The combinatorics of an arrangement of m tropical pseudohyperplanes in the tropical space T n-1 is captured by its TOM. The Topological Representation Theorem establishes a correspondence between TOMs (with parameters (m, n)) and subdivisions of

∆ m-1 × ∆ n-1 [AD09, Hor12, OY11].
If M is a TOM of an arrangement whose pseudohyperplanes have labels in [m], denote by M| S the TOM of the subarrangement corresponding to the hyperplanes with labels in S ⊆ [m]. This turns Theorems 4.2 and 4.3 into the following statements, respectively.

Corollary 1.2. For each S ∈ [m] n+1 , let M S be the TOM of a generic arrangement of n + 1 pseudohyperplanes in T n-1 with labels in S. If the matroids in this collection are compatible, i.e. M S | S∩T = M T | S∩T for every T, S ∈ [m] n+1 , then there exists a unique arrangement of m pseudohyperplanes in T n-1 whose TOM M fulfills M| S = M S .

Corollary 1.3. There exists a collection of pairwise compatible TOMs on the subsets in [n+1] n that cannot be completed to the TOM of an arrangement of n + 1 pseudohyperplanes in T n-1 .

These corollaries should be compared with analogue results in classical oriented matroid theory: every oriented matroid of rank n -1 is completely determined by its submatroids with n elements, and every compatible collection of submatroids with n + 1 elements can be completed to a full oriented matroid (cf. [BLS + 93, Corollaries 3.6.3 and 3.6.4]).

On the other hand, Theorem 4.2 can be regarded as a "finiteness" result for triangulations of ∆ m-1 × ∆ n-1 : it says that, as long as m ≥ n + 1, triangulations of ∆ m-1 × ∆ n-1 are "built" from the collection of triangulations of ∆ n × ∆ n-1 , no matter how large m is. From this viewpoint, Theorem 4.2 should be contrasted with recent results in commutative algebra regarding finiteness properties of the generating sets of certain families of polynomial ideals (see, for instance, [START_REF] Christopher | Finite Gröbner bases in infinite dimensional polynomial rings and applications[END_REF][START_REF] Hos ¸ten | A finiteness theorem for Markov bases of hierarchical models[END_REF][START_REF] Snowden | Syzygies of Segre embeddings and ∆-modules[END_REF]).

Here is the layout of this extended abstract. The next section contains some preliminaries concerning notation and representations for triangulations of products of simplices. The Dyck path triangulation is then presented in Section 3, along with the explicit construction behind Theorem 4.3. Finally, Section 4.1 contains the proof of our extendability results; in particular, Theorems 4.2 and 4.3.

Preliminaries

In this section, in order to set our notation and conventions, we recall some well-known facts related to triangulations of ∆ m-1 × ∆ n-1 (we refer to [DRS10, Section 6.2] for a more detailed exposition).

1 1 2 2 3 [3] [2] 1 1 2 2 3 [3] [2] 1 1 2 2 3 [3] [2] 1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 (e1,e1) (e2,e1) (e1,e3) (e1,e2) (e2,e3) (e2,e2)

Bipartite graphs and the matching ensemble representation

Let K m,n be the complete bipartite graph on m + n vertices, whose parts we label by [m] and [n] (i) . A vertex (e i , e j ) of ∆ m-1 × ∆ n-1 can be represented as the undirected edge (i, j) of K m,n . Every triangulation of ∆ m-1 × ∆ n-1 gives rise to a collection of subgraphs of K m,n , each one indexing the vertex set of a maximal simplex of the triangulation. As it turns out, this collection (and hence also the triangulation) is completely determined by the matchings contained in these subgraphs.

(i) Throughout we use overlined numbers and variables to distinguish the vertices of both factors of ∆ m-1 × ∆ n-1 .

Recently, Suho Oh and Hwanchul Yoo [START_REF] Oh | Triangulations of ∆ n-1 × ∆ d-1 and Matching Ensembles[END_REF] have found a concise characterization of the collections of perfect matchings that correspond to triangulations of ∆ m-1 × ∆ n-1 , hence discovering a novel matching ensemble representation for triangulations of ∆ m-1 × ∆ n-1 .

4]).

There is a bijection between matching ensembles of K m,n and triangulations of ∆ m-1 × ∆ n-1 .

Grid representation

The m × n grid, which we denote by G m×n , is a rectangular array of width m and height n composed of mn unit squares. Every unit square in G m×n has a position (i, j) in the grid, where index i increases to the right and index j increases upwards. Thus, the vertex (e i , e j ) in ∆ m-1 × ∆ n-1 is represented by the square at position (i, j) in G m×n . The grid representation of a triangulation of ∆ m-1 × ∆ n-1 is the collection of grids representing the vertex sets of the maximal simplices of the triangulation.

Mixed subdivisions

In order to illustrate some of our constructions, we shall draw triangulations of ∆ m-1 ×∆ n-1 as fine mixed subdivisions of m∆ n-1 . Let T be a triangulation of ∆ m-1 × ∆ n-1 . To each simplex s ∈ T associate the simplex s i = conv {e j : (e i , e j ) ∈ s} ⊂ ∆ n-1 . The set of Minkowski sums {s 1 + • • • + s m : s ∈ T } forms a mixed subdivision of m∆ n-1 . The Cayley trick states that this correspondence is a bijection between triangulations of ∆ m-1 × ∆ n-1 and fine mixed subdivisions of m∆ n-1 (see [START_REF] Santos | The Cayley trick and triangulations of products of simplices. Integer Points in Polyhedra -Geometry[END_REF] for more details).

The Dyck path triangulation and some relatives

There are two main ingredients towards our construction for Theorem 4.3: the Dyck path triangulation and the extended Dyck path triangulation. We present them here, together with a generalized version.

The Dyck path triangulation

The first ingredient is a triangulation of ∆ n-1 × ∆ n-1 that we call the Dyck path triangulation and denote by D n . This triangulation can be described in terms of Dyck paths in the grid representation, that is, monotonically increasing paths from the square (1, 1) to the square (n, n) of G n×n , in which every square (i, j) satisfies i ≤ j. The maximal simplices of D n are the Dyck paths in G n×n , together with the orbit of simplices they generate under an action that cyclically shifts the indices in both factors of ∆ n-1 × ∆ n-1 simultaneously. An example for n = 3 is depicted in Figure 4(a). The perfect matching representation of D n is also easy to describe. We begin with the set of all perfect matchings on the subgraphs of K n,n induced by I ⊂ [n], J ⊂ [n] (with |I| = |J|) which are non-crossing (nc) and weakly increasing (wi), that is, those matchings m that satisfy i < i ⇒ j < j for every (i, j), (i , j ) ∈ m, i ≤ j for every (i, j) ∈ m .

Next, for ∈ [n], we introduce the collection of matchings of the form

i + (mod n), j + (mod n) : (i, j) ∈ m, m fulfills (nc+wi) , (cyc)
obtained by "cyclically shifting" the indices of the perfect matchings that satisfy (nc+wi), and call M n the set of all matchings obtained after ranging over all ∈ [n] (see Figure 5).

Fig. 5: A perfect matching on K {1,2,5},{2,4,5} satisfying (nc+wi), together with its cyclic orbit (cyc).

Due to lack of space, we omit the proof of the following theorem and refer to [START_REF] Ceballos | Dyck path triangulations and extendability[END_REF] for details.

Theorem 3.1. The collection of matchings M n constitutes a matching ensemble of K n,n , and its associated triangulation of ∆ n-1 × ∆ n-1 is the Dyck path triangulation D n . Moreover, D n is a regular triangulation, which can be obtained by the height function h : ∆ n-1 × ∆ n-1 → R that assigns to the point (e i , e j ) the height h ij = c j-i (mod n) , for some real number c > 1 sufficiently large.

Remark 3.2. The Dyck path triangulation of ∆ n-1 × ∆ n-1 is a natural refinement of a coarse regular subdivision introduced by Gelfand, Kapranov and Zelevinsky in [GKZ94, Example 3.14]. Indeed, the union of all Dyck paths is a cell of this subdivision, and the remaining cells are obtained by applying the cyclic action that shifts the indices. For us, the crucial property of D n that underlies the construction for Theorem 4.3, is that it admits a geometric bistellar flip supported on the circuit C = (C + , C -) of maximal dimension given by C + := {(e 1 , e 2 ), (e 2 , e 3 ), . . . , (e n-1 , e n ), (e n , e 1 )}

(1)

C -:= {(e 1 , e 1 ), (e 2 , e 2 ), . . . , (e n-1 , e n-1 ), (e n , e n )}.

Therefore, performing this flip consists in replacing only the simplices in

T + := {C \ {v} : v ∈ C + } ⊂ D n by those in T -:= {C \ {v} : v ∈ C -},

The extended Dyck path triangulation

The second ingredient is a natural extension of D n to a triangulation of ∆ n × ∆ n-1 , which we call the extended Dyck path triangulation and denote by D ext n . In the grid representation, an extended Dyck path is formed by several Dyck paths, concatenated one after the other in the grid G (n+1)×n , and a square in the (n + 1)-th column and last row of each Dyck path; this is illustrated in Figure 6(a). The maximal simplices of D ext n are given by the extended Dyck paths in G (n+1)×n , together with the orbit of simplices they define under an action that cyclically shifts the indices in both factors of

∆ [n] × ∆ n-1 ⊂ ∆ n × ∆ n-1
simultaneously (note that here the action ignores the (n + 1)-th vertex of the first factor). The simplices of the extended Dyck path triangulation for n = 3 are shown in Figure 6(b). Interestingly, the simplices obtained this way constitute a regular triangulation of ∆ n × ∆ n-1 .

We can similarly describe its matching ensemble. Now we start with the set of matchings m between I ⊂ [n + 1] and J ⊂ [n] with the property i < i ⇒ j < j for every (i, j), (i , j ) ∈ m, i ≤ j for every (i, j) ∈ m with i = n + 1.

(nc+wi ext )

As before, we consider the set of perfect matchings on induced subgraphs of K n+1,n of the form

ρ (i), j + (mod n) : (i, j) ∈ m, m fulfills (nc+wi ext ) , ( cyc ext )
where ρ (i

) := i + (mod n) if i = n + 1 n + 1 otherwise ,
with ranging over [n], and denote it by M ext n . Theorem 3.3. The collection of matchings M ext n constitutes a matching ensemble of K n+1,n , and its associated triangulation of ∆ n × ∆ n-1 is the extended Dyck path triangulation D ext n . Moreover, D ext n is a regular triangulation, and can be obtained by assigning the height h ij to the point (e i , e j ), defined by:

h ij =      c j-i if j ≥ i c n+j-i if j < i < n + 1 1 if i = n + 1; (2)
where c > 1 is a sufficiently large real number.

Again, we refer to [START_REF] Ceballos | Dyck path triangulations and extendability[END_REF] for the complete proof of this statement.

The generalized Dyck path triangulations

Dyck path triangulations have a natural generalization to triangulations D (rn,n) of ∆ rn-1 × ∆ n-1 for any r > 0. This shows an interesting connection to rational Catalan combinatorics (cf. [AHJ13, ARW13]). Define an (rn, n)-Dyck path (ii) in the grid G rn×n as a monotonically increasing path from (1, 1) to (rn, n) such that every step (i, j) satisfies i ≤ rj.

The (rn, n)-Dyck path triangulation D (rn,n) is the triangulation of ∆ rn-1 ×∆ n-1 that has as maximal simplices the (rn, n)-Dyck paths together with their orbits under the action that maps (i, j) → (i + r (mod rn), j + 1 (mod n)). An example is illustrated in Figure 7.

Theorem 3.4. The (rn, n)-Dyck path triangulation D (rn,n) is a triangulation of ∆ rn-1 × ∆ n-1 . Moreover, it is regular. (ii) The standard definition of a rational (a, b)-Dyck path is slightly different: it uses a grid from (0, 0) to (a, b) and imposes that the lattice points in the path are above the main diagonal. It is used, for example, in [START_REF] Armstrong | Rational associahedra and noncrossing partitions[END_REF].

4 Extendability of partial triangulations

Extendable partial triangulations

In order to present the proof of our extendability Theorem 4.2, we first observe that, whenever m ≥ k ≥ n, if a triangulation of

∆ (k-1)
m-1 × ∆ n-1 extends to a triangulation of ∆ m-1 × ∆ n-1 , then this extension is unique. We omit the proof, which can be easily deduced from Theorem 2.2 (it is also implicit in the proof of a classical result of Dey, cf. [Dey93, Section 3] and [DRS10, Lemma 8.4.1]).

(k-1) m-1 × ∆ n-1 extends to a unique triangulation of ∆ m-1 × ∆ n-1 . Proof. Let T be a triangulation of ∆ (k-1)
m-1 × ∆ n-1 in the conditions of the theorem, and let M be the set of all perfect matchings contained in the simplices of T , when viewed as subgraphs of K m,n . We prove that M is necessarily a matching ensemble (cf. Definition 2.1) and hence, by Theorem 2.2, that it is the family of perfect matchings of a triangulation of ∆

m-1 × ∆ n-1 . (SA). For each I ⊂ [n], J ⊂ [m] with |I| = |J| ≤ n, the restriction T | ∆ I ×∆ J is a triangulation of the face ∆ I × ∆ J of ∆ m-1 × ∆ n-1 .
Let M| K I,J be the set of perfect matchings associated to this restricted triangulation. Since this face is a product of simplices, Theorem 2.2 applies, so that there is a unique perfect matching m ∈ M| K I,J on the induced subgraph K I,J .

(CA). Again, for each perfect matching m ∈ M on K I,J , T | ∆ I ×∆ J is a legal triangulation, as are all of its restrictions. In particular, by Theorem 2.2, it follows that m ∈ M whenever m ⊆ m.

(LA). Fix a perfect matching m ∈ M on K I,J , where |I| = |J| ≤ n, and let

v ∈ ([m] ∪ [n]) \ ([I] ∪ [J]). Observe that T | ∆ I∪v ×∆ J (resp. T | ∆ I ×∆ J∪v ) is a legal triangulation, because k ≥ n + 1.
In particular, that means that there are two edges e ∈ K I∪v,J (resp. e ∈ K I,J∪v ) and e ∈ m sharing a common vertex such that v ∈ e and (m \ e ∪ e ) ∈ M.

Finally, the uniqueness of the resulting triangulation was established in Lemma 4.1.

Non-extendable partial triangulations

The restriction of Suppose, for the sake of absurdity, that axiom (LA) holds for m ∈ M . Then, there is a unique perfect matching m ∈ M on K [n]\w∪n+1,[n] that differs from m in a single edge. However, letting w = n ∈ [n] (which we may by symmetry), we see that the unique perfect matching on K

D ext n to ∂ (∆ n ) × ∆ n-1 gives a partial triangulation of ∆ n × ∆ n-1 whose restriction to the facet ∆ [n] × ∆ n-

Fig. 1 :

 1 Fig. 1: The Dyck path triangulation of ∆2 × ∆2 drawn as a subdivision of 3∆2.

  × ∆ n-1 was first systematically considered for k = 2 by Ardila and Ceballos in [AC13], who completely characterized the extendable triangulations of ∆ (1) 2 × ∆ n-1 . There, in an attempt to prove the Spread Out Simplices Conjecture of Ardila and Billey [AB07, Conjecture 7.1], the authors formulated the Acyclic System Conjecture [AC13, Conjecture 5.7], which concerned a sufficient condition for the extendability of triangulations of ∆ (1)

Fig. 3 :

 3 Fig. 3: Several representations of a triangulation of ∆1 × ∆2.

  Definition 2.1 ([OY13, Definition 4.1]). A family of perfect matchings M on the subgraphs of K m,n induced by vertex sets I ∪ J, where I ⊂ [m], J ⊂ [n] and |I| = |J|, is a matching ensemble if: (SA). for each I ⊂ [m] and J ⊂ [n] with |I| = |J|, there exists a unique m ∈ M on the subgraph of K m,n induced by I and J (supports axiom), (CA). for each m ∈ M and for each (perfect sub-matching) m ⊆ m, m ∈ M (closure axiom), and (LA). for each m ∈ M and for each v ∈ [n] ∪ [m] \ (I ∪ J), there are two edges e ∈ K m,n and e ∈ m sharing a common vertex such that v ∈ e and (m \ e ∪ e ) ∈ M (linkage axiom).Theorem 2.2 ([OY13, Theorem 5.

( a )Fig. 4 :

 a4 Fig. 4: The Dyck path triangulation of ∆2 × ∆2 and its flipped version in the grid and mixed subdivisions representations.

  (a) An extended Dyck path, representing a full-dimensional simplex in D ext n . (b) The triangulation D ext 3 of ∆ 3 × ∆ 2 in the grid and mixed subdivision representations.

Fig. 6 :

 6 Fig. 6: Illustration of the extended Dyck path triangulation D ext n .

  while leaving the rest of D n intact; in particular, the flip does not alter the restriction of D n to the boundary of ∆ n-1 × ∆ n-1 . We refer the reader to [DRS10, Section 4.4.1] for the precise definition of a geometric bistellar flip. We call the resulting triangulation the flipped Dyck path triangulation, and denote it by D flip n ; it is illustrated for n = 3 in Figure 4(b).

  Mixed subdivision representation of D (6,3) and D ext (6,3) .(b) Grid representation of D (6,3) .

Fig. 7 :

 7 Fig. 7: The triangulation D (6,3) and its extension D ext (6,3) .

Lemma 4. 1 .

 1 Let m, n, k be natural numbers such that n ≥ 2 and m ≥ k ≥ n. Every triangulation of ∆ m-1 × ∆ n-1 is uniquely determined by its restriction to∆ (k-1) m-1 × ∆ n-1 . Not every triangulation of ∆ (k-1) m-1 × ∆ n-1 can be extended to a triangulation of ∆ m-1 × ∆ n-1 ,as is already known from the familiar non-extendable triangulation of ∆ (1) 2 × ∆ 1 depicted in Figure 2(a), often called "the mother of all examples". However, by strengthening the hypotheses to k > n, it becomes possible to certify extendability. Theorem 4.2. Let m, n, k be positive integers such that m ≥ k > n. Every triangulation of ∆

  1 coincides with D n . Denote by ∂(D ext n ) this restricted triangulation, whose facet ∆ [n] × ∆ n-1 admits a bistellar flip supported on the circuit (1). By this, we mean that the triangulation of the facet ∆ [n] × ∆ n-1 can be changed from D n to D flip n , without affecting the triangulation of the remaining facets of ∂ (∆ n ) × ∆ n-1 . Hence, the result of the flip is still a triangulation of ∂ (∆ n ) × ∆ n-1 , which we call flipped extended Dyck path triangulation and denote ∂(D ext n ) flip . An example is depicted in Figure 8.

Fig. 8 :

 8 Fig. 8: A non-extendable triangulation ∂(D ext n ) flip of ∂ (∆3) × ∆3-1.Theorem 4.3. The flipped extended Dyck path triangulation∂(D ext n ) flip of ∂ (∆ n )×∆ n-1 is non-extendable. Proof. The triangulation ∂(D ext n ) flip of ∂ (∆ n ) × ∆ n-1 produces a collection of perfect matchings on all induced subgraphs of K n+1,n , that we refer to as M (for which the reader can check that the axioms (SA) and (CA) hold). Observe that, by construction, M ext n and M agree on all the induced subgraphs K I,[n] , where n / ∈ I ⊂ [n + 1]. In contrast, the triangulation D flip n of ∆ n-1 × ∆ n-1 contributes the following matching on the induced subgraph K [n],[n] : m := {(1, 2), (2, 3), (3, 4), . . . , (n -1, n), (n, 1)}.

  [n]\w∪n+1,[n] in the matching ensemble M ext n is {(1, 1), (2, 2), (3, 3), . . . , (n -1, n -1), (n + 1, n)},so m cannot satisfy axiom (LA). Therefore, M is not a matching ensemble and ∂(D ext n ) flip cannot be extended to a triangulation of ∆ n × ∆ n-1 .Corollary 4.4. For every m ≥ n there exist non-extendable triangulations of ∆ (n-1) m × ∆ n-1 .

Acknowledgements

The authors want to thank Francisco Santos for many interesting and enlightening conversations.

‡ Supported by the government of Canada through a Banting Postdoctoral Fellowship. He was also supported by a York University research grant. URL: http://garsia.math.yorku.ca/ ˜ceballos/ § Supported by the DFG Collaborative Research Center SFB/TR 109 "Discretization in Geometry and Dynamics". URL: http://page.mi.fu-berlin.de/arnaupadrol/ ¶ Partially supported by the IMPRS of the Max Planck Institute for Mathematics in the Sciences, Leipzig, and by the CDS, Magdeburg. URL: http://www-e.uni-magdeburg.de/sarmient/ 1365-8050 c 2015


Rebecca Patrias
email: patri080@umn.edu

Pavlo Pylyavskyy

Dual filtered graphs

Keywords: dual graded graphs, K-theory, bialgebras

Introduction

Fomin's dual graded graphs [START_REF] Fomin | Duality of graded graphs[END_REF]), as well as their predecessors -Stanley's differential posets [START_REF] Stanley | Differential posets[END_REF]), were invented as a tool to better understand the Robinson-Schensted insertion algorithm. Dual graded graphs are significant in the areas where the Robinson-Schensted correspondence appears, for example in Schubert calculus or in the study of representations of towers of algebras [START_REF] Begeron | Combinatorial hopf algebras and towers of algebras: dimension, quantization and functoriality[END_REF]; Björner and Stanley). A recent work of [START_REF] Lam | Dual graded graphs for Kac-Moody algebras[END_REF] associates a dual graded graph to any Kac-Moody algebra, bringing their study to a new level of generality.

Weyl algebra and its deformations

One way to view the theory is as a study of certain combinatorial representations of the first Weyl algebra. Let us briefly recall the definitions. The Weyl algebra, or the first Weyl algebra, is an algebra over some field K (usually K = R) generated by two generators U and D with a single relation DU -U D = 1. It was originally introduced by Hermann Weyl in his study of quantum mechanics. We refer the reader to [START_REF] Bjork | Rings of differential operators[END_REF], for example, for more background on the Weyl algebra.

A graded graph is a triple G = (P, ρ, E), where P is a discrete set of vertices, ρ : P → Z is a rank function, and E is a multiset of edges/arcs (x, y), where ρ(y) = ρ(x) + 1. In other words, each vertex is assigned a rank, and edges can only join vertices in successive ranks. For the set of vertices P , let P n denote the subset of vertices of rank n. For any field K of characteristic zero, the formal linear combinations of vertices of G form the vector space KP .

Let G 1 = (P, ρ, E 1 ) and G 2 = (P, ρ, E 2 ) be a pair of graded graphs with a common vertex set and rank function. From this pair, define an oriented graded graph G = (P, ρ, E 1 , E 2 ) by orienting the edges of G 1 in the direction of increasing rank and the edges of G 2 in the direction of decreasing rank. Let a i (x, y) denote the number of edges of E i joining x and y or the multiplicity of edge (x, y) in E i . We define the up and down operators U, D ∈ End(KP ) associated with graph G by

U x = y a 1 (x, y)y and Dy = x a 2 (x, y)x.
Graded graphs G 1 and G 2 with a common vertex set and rank function are said to be dual if

DU -U D = I,
where I is an identity operator acting on KP . Thus, we see that KP is a representation of the Weyl algebra. Furthermore, it is a representation of a very special kind, where U and D act in a particularly nice combinatorial way on a fixed basis.

One would then expect that variations of the Weyl algebra would correspond to some variations of the theory of dual graded graphs. One such variation is the q-Weyl algebra defined by the relation

DU -qU D = 1.
The corresponding theory of quantum dual graded graphs was pursued in [START_REF] Lam | Quantized dual graded graphs[END_REF].

In this paper, we shall study the theory arising from an analogue W of the Weyl algebra with defining relation

DU -U D = D + 1.
We shall refer to it as the Ore algebra Ore (1933), and we shall see that it is a very natural object. In particular, the corresponding theory of dual filtered graphs fits naturally with the existing body of work on the K-theory of Grassmannians. Note that it is easy to see that by rescaling U and D, we can pass from arbitrary DU -U D = αD + β to DU -U D = D + I. We thus suffer no loss in generality by writing down the relation in the latter form.

Pieri and M öbius constructions

We make use of two conceptual ways to build examples of dual filtered graphs. The first construction starts with an algebra A, a derivation D on A, and an element f ∈ A such that D(f ) = f + 1. We often build the desired derivation D using a bialgebra structure on A. This construction is very close to an existing one in the literature [START_REF] Begeron | Combinatorial hopf algebras and towers of algebras: dimension, quantization and functoriality[END_REF]; [START_REF] Nzeutchap | Dual graded graphs and Fomin's r-correspondences associated to the Hopf algebras of planar binary trees, quasi-symmetric functions and noncommutative symmetric functions[END_REF]; Lam and Shimozono), where dual graded graphs are constructed from graded Hopf algebras. In fact, if we were to require D(f ) = 1, we would get dual graded graphs instead of dual filtered graphs in our construction. We refer to this method as the Pieri construction or sometimes as the Pieri deformation.

Instead, we can also start with an existing dual graded graph G = (P, ρ, E 1 , E 2 ) (see definition below), composed of graphs G 1 = (P, ρ, E 1 ) and G 2 = (P, ρ, e 2 ), and adjust E 1 and E 2 in the following manner. To obtain G 1 , we add #{x|y covers x in G 1 } loops at each vertex y ∈ P to E 1 . As for G 2 , we create a new edge set E 2 by forming a 2 (x, y) = |µ(x, y)| edges between vertices x and y, where µ denotes the Möbius function in G 2 = (P, ρ, E 2 ). We refer to this construction as the Möbius construction or Möbius deformation. Note that this does not always produce a pair of dual filtered graphs, and it is mysterious to determine when it does. In some major examples, however, it is the result of this construction that relates to Robinson-Schensted-like algorithms, for example to Hecke insertion of [START_REF] Buch | Stable Grothendieck polynomials and K-theoretic factor sequences[END_REF].

The following observation seems remarkable, and we call it the Möbius via Pieri phenomenon. Let A be a graded Hopf algebra, and let bialgebra à be its K-theoretic deformation in some appropriate sense which we do not know how to formalize. Let G be a natural dual graded graph associated with A. What we observe is that applying the Möbius construction to G yields the same result as a natural Pieri construction applied to Ã. In other words, the following diagram commutes.

A Ã G G Möbius construction Pieri construction Pieri construction K deformation
This happens for Young's lattice, see Section 4.4, and for the binary tree dual graded graph, see Section 5.1.

The crucial condition necessary for this phenomenon to be observed is for A to be the associated graded algebra of Ã, but this is not always the case. For example, this is not the case for the K-theoretic analogue of the Poirier-Reutenauer Hopf algebra, see Section 5.3. To put it simply, the numbers of basis elements for the filtered components of A and à are distinct in those cases, thus there is no hope to obtain corresponding graphs one from the other via Möbius construction. Interestingly, those are exactly the examples we found where the Möbius construction fails to produce a dual filtered graph.

Dual graded graphs

This section follows [START_REF] Fomin | Duality of graded graphs[END_REF], and we refer the reader to this source for further reading.

A graded graph is a triple G = (P, ρ, E), where P is a discrete set of vertices, ρ : P → Z is a rank function, and E is a multiset of edges/arcs (x, y), where ρ(y) = ρ(x) + 1. In other words, each vertex is assigned a rank, and edges can only join vertices in successive ranks. For any field K of characteristic zero, the formal linear combinations of vertices of G form the vector space KP .

Example 2.1 Young's lattice is an example of a graded graph where for any partition λ, ρ(λ) = |λ|, and there is an edge from λ to µ if µ can be obtained from λ by adding one box. Ranks zero through four are shown below. We see that (3, 31) ∈ E andρ(3) + 1 = 3 + 1 = ρ(31) = 4 Let G 1 = (P, ρ, E 1 ) and G 2 = (P, ρ, E 2 ) be a pair of graded graphs with a common vertex set and rank function. From this pair, define an oriented graded graph G = (P, ρ, E 1 , E 2 ) by orienting the edges of G 1 in the direction of increasing rank and the edges of G 2 in the direction of decreasing rank. Let a i (x, y) denote the number of edges of E i joining x and y or the multiplicity of edge (x, y) in E i . We define the up and down operators U, D ∈ End(KP ) associated with graph G by Graded graphs G 1 and G 2 with a common vertex set and rank function are said to be dual if

U x =
DU -U D = I.
Example 2.2 Young's lattice is an example of a self-dual graded graph.

Dual filtered graphs

A weak filtered graph is a triple G = (P, ρ, E), where P is a discrete set of vertices, ρ : P → Z is a rank function, and E is a multiset of edges/arcs (x, y), where ρ(y) ≥ ρ(x). A strict filtered graph is a triple G = (P, ρ, E), where P is a discrete set of vertices, ρ : P → Z is a rank function, and E is a multiset of edges/arcs (x, y), where ρ(y) > ρ(x). Let P n as before denote the subset of vertices of rank n.

Let G 1 = (P, ρ, E 1 ) and G 2 = (P, ρ, E 2 ) be a pair of filtered graphs with a common vertex set, G 1 weak while G 2 strict. From this pair, define an oriented filtered graph G = (P, E 1 , E 2 ) by orienting the edges of G 1 in the positive filtration direction and the edges of G 2 in the negative filtration direction. Recall that a i (x, y) denotes the number of edges of E i joining x and y or the multiplicity of edge (x, y) in E i . Using the up and down operators associated with graph G as previously defined, we say that G 1 and G 2 are dual filtered graphs if DU -U D = D + I.

In the next sections, we describe three constructions of dual filtered graphs. For proofs of the following results, see Patrias and Pylyavskyy (2014b).

Trivial construction

Every dual graded graph has an easy deformation that makes it a dual filtered graph. To construct it, simply add ρ(x) "upward" loops to each element x of the dual graded graph, where ρ is the rank function. We will call this the trivial construction.

Pieri construction

The following construction is close to the one for dual graded graphs described in the works of [START_REF] Begeron | Combinatorial hopf algebras and towers of algebras: dimension, quantization and functoriality[END_REF], [START_REF] Nzeutchap | Dual graded graphs and Fomin's r-correspondences associated to the Hopf algebras of planar binary trees, quasi-symmetric functions and noncommutative symmetric functions[END_REF], and Lam and Shimozono. Let A = ⊕ i≥0 A i be a filtered, commutative algebra over a field F with A 0 = F and a linear basis a λ ∈ A |λ| . Here, the λ's belong to some infinite indexing set P , where each graded component,

P i = {λ | |λ| = i}, is finite. The property of being filtered means that a λ a µ = c ν a ν , where |λ| + |µ| ≤ |ν|. Let f = f 1 + f 2 + . . . ∈  be an element of the completion  of A such that f i ∈ A i . Assume D ∈ End(A) is a derivation on A satisfying D(f ) = f + 1.
To form a graph, we define E 1 by defining a 1 (λ, µ) to be the coefficient of a λ in D(a µ ). We also define E 2 by defining a 2 (λ, µ) to be the coefficient of a µ in a λ f. Theorem 3.3 The resulting graph is a dual filtered graph.

The result follows from D(f a λ ) = D(f )a λ + f D(a λ ), or D(f a λ ) -f D(a λ ) = a λ + D(a λ ). Now, assume A 1 is one-dimensional,
and let g be its generator. We shall often find a derivation D from a bialgebra structure on A. Indeed, assume ∆ is a coproduct on A such that ∆(a) = 1 ⊗ a + a ⊗ 1 + . . . , where the rest of the terms lie in (A 1 ⊕ A 2 ⊕ . . .) ⊗ (A 1 ⊕ A 2 ⊕ . . .). Assume also ξ is a map A ⊗ A -→ A such that ξ(p ⊗ g) = p and for any element q ∈ A i , i = 1, we have ξ(p ⊗ q) = 0.

M öbius construction

Let G = (P, ρ, E 1 , E 2 ) be a dual graded graph. From G, form a pair of filtered graphs as follows. Let G 1 = (P, ρ, E 1 ) have the set of edges E 1 consisting of the same edges as E 1 plus #{x|y covers x in G 1 } loops at each vertex y ∈ P . Let G 2 = (P, ρ, E 2 ) have the set of edges E 2 consisting of a 2 (x, y) = |µ(x, y)| edges between vertices x and y, where µ denotes the Möbius function in (P, ρ, E 2 ). Compose G 1 and G 2 into an oriented filtered graph G.

In many cases, including that of Young's lattice, the Möbius construction results in a dual filtered graph. However, it does not always do so. Unlike with the Pieri construction, we do not have the algebraic machinary explaining why this is so. Instead, we provide the proofs on a case-by-case basis. Nevertheless, the Möbius construction is the most important one, as it is this construction that relates to insertion algorithms and thus to K-theory of Grassmannians and Lagrangian Grassmannians.

Young's lattice

A Pieri deformation of Young's lattice

Let A = Λ be the ring of symmetric functions. Let s λ , p λ , and h λ be its bases of Schur functions, power sum symmetric functions, and complete homogeneous symmetric functions. Let

f = h 1 + h 2 + . . . .
Define up and down edges of a filtered graph G = (P, ρ, E 1 , E 2 ) by letting a 1 (µ, ν) be the coefficient of s ν in p 1 s µ , and a 2 (µ, ν) be the coefficient of s ν in f s µ .

Recall that given two partitions, µ and ν, µ/ν forms a horizontal strip if no two boxes of µ/ν lie in the same column. For example, (4, 2, 1)/(2, 1) forms a horizontal strip while (4, 3, 1)/(2, 1) does not.

Lemma 4.1 The up edges E 1 coincide with those of Young's lattice, while the down edges E 2 connect shapes that differ by a horizontal strip.

In the figure below, the first six ranks are shown. The edges in the graph on the left are upward-oriented, and the edges on the graph on the right are downward-oriented. We prove this theorem using the fact the Λ is a free polynomial ring in p 1 , p 2 , . . ., which can be endowed with a standard bilinear inner product determined by s λ , s µ = δ λ,µ . We then show that for any h, g ∈ Λ we have g, p 1 h = d dp1 g, h and d dp1 f = f + 1. Now, we see that A = Λ, a λ = s λ , D = d dp1 , and f = h 1 + h 2 + . . . satisfy the conditions of Theorem 3.3. The claim follows.

M öbius deformation of Young's lattice

Given two partitions, λ and ν, λ/ν forms a rook strip if no two boxes of λ/ν lie in the same row and no two boxes of λ/ν lie in the same column. In other words, λ/ν is a rook strip if it is a disconnected union of boxes. It is well known that in Young's lattice, |µ(λ, ν)| = 1 if ν/λ is a rook strip and is 0 otherwise, see Example 3.9.6 in [START_REF] Stanley | Enumerative Combinatorics[END_REF]. Using this fact, we can use the Möbius construction to form the pair of filtered graphs from Young's lattice shown below.

Hecke insertion

In [START_REF] Buch | Stable Grothendieck polynomials and K-theoretic factor sequences[END_REF], Buch, Kresch, Shimozono, Tamvakis, and Yong introduce a K-theoretic analogue of the RSK algorithm called Hecke insertion and reverse Hecke insertion that corresponds to the Möbius deformation of Young's lattice in the same way that RSK corresponds to Young's lattice. In other words, if we insert a word w of length n using Hecke insertion, the construction of the insertion tableau will be represented as a path of length n downward that ends at ∅ in the Möbius deformation of Young's lattice, and the construction of the recording tableau is represented as a path of length n upward starting at ∅.

In this setting, the proper K-theoretic analogues of standard Young tableaux are increasing tableaux [START_REF] Thomas | A jeu de taquin theory for increasing tableaux, with applications to K-theoretic Schubert calculus[END_REF]) and set-valued tableaux [START_REF] Björner | A Littlewood Richardson rule for K-theory of Grassmannians[END_REF]), acting as insertion and recording tableaux, respectively. See Patrias and Pylyavskyy (2014a) for details about this correspondence.

M öbius via Pieri

The following shows that we have an instance of the Möbius via Pieri phenomenon in the case of Young's lattice. Namely, the Möbius deformation of Young's lattice is obtained by the Pieri construction from an appropriate K-theoretic deformation of the underlying Hopf algebra.

Take A to be the subring of the completion Λ of the ring of symmetric functions with basis {G λ }, the stable Grothendieck polynomials. For details, see [START_REF] Björner | A Littlewood Richardson rule for K-theory of Grassmannians[END_REF] and [START_REF] Lam | Combinatorial Hopf algebras and K-homology of grassmannians[END_REF]. Let S µ be the superstandard tableau of shape µ, that is, the first row of S is filled with 1, 2, . . . , µ 1 , the second row with µ 1 + 1, m 1 + 2, . . . , µ 1 + µ 2 , etc. This space has a bialgebra structure reminiscent of that of the Λ with Hecke insertion taking the role of RSK insertion. We refer the reader to [START_REF] Buch | k-theory of miniscule varieties[END_REF], Patrias and Pylyavskyy (2014a), and [START_REF] Thomas | The direct sum map on grassmannians and jeu de taquin for increasing tableaux[END_REF] for details.

We consider the following Pieri construction in A. Let g = G 1 , and define an operator D by D(G ν ) = ξ(∆(G ν )). We define a graph G, where elements are partitions, a 1 (µ, λ) is the absolute value of the coefficient of G µ in D(G λ ), and a 2 (µ, λ) is the absolute value of the coefficient of G λ in G µ G 1 . It is not hard to show the result is the same as the Möbius deformation of Young's lattice using the bialgebra structure.

Proposition 4.4 The resulting graph coincides with the one obtained via Möbius construction in Section 4.2.

Binary tree deformations

A Pieri deformation of BinW ord

The lifted binary tree is shown on the left, where vertices can be naturally labeled by bit strings: 0, 1, 10, 11, 100, 101,. . .. The graph BinWord with the same set of vertices and rank function is shown on the right. In BinWord, an element x covers y if y can be obtained from x by deleting a single digit from x, and in addition, 1 covers 0. The lifted binary tree and BinWord form a dual graded graph, see (Fomin, 1994, Example 2.4.1). We form a Pieri deformation by interpreting the graph in the context of the ring of quasisymmetric functions, QSym (see [START_REF] Stanley | Enumerative Combinatorics[END_REF]). If we interpret "1" as L 1 , "10" as L 2 , "100" as L 3 , 11001 as L 131 , and so on, we see that x covers y in the graph on the right exactly when x appears in the product L y • L 1 , where L α is the fundamental quasisymmetric function with the usual product. Let D be the operator that subtracts 1 from the rightmost number in the subscript or deletes the rightmost number if it is 1. For example, D(L 14 ) = L 13 and D(L 1421 ) = L 142 . Then x covers y in the graph on the left exactly when y = D(x). To form the Pieri deformation, we can let f = L 1 + L 11 + L 111 + . . .. In other words, the multiplicity of the edge from x down to y is the coefficient of x in y • (L 1 + L 11 + . . .). Using A = QSym and D and f as defined above, it is easy to see that D(f ) = L ∅ + f = id + f . Using the Hopf algebra structure of QSym, it is clear that D is a derivation by Lemma 3.4. Thus the resulting graph is a dual filtered graph by Theorem 3.3.

M öbius via Pieri

Consider the Hopf algebra of multi-quasisymmetric functions, mQSym, defined in [START_REF] Lam | Combinatorial Hopf algebras and K-homology of grassmannians[END_REF]. This Hopf algebra is a natural K-analogue of the Hopf algebra of quasisymmetric functions and has a basis of multi-fundamental quasisymmetric functions indexed by compositions, { Lα }. Notice that a graph with vertices indexed by { Lα } has the same vertices as in Section 5.1.

The product of Lα and Lβ mQSym is obtained by first identifying permutations, w α and w β , where the composition of the descent set is α and β, respectively, taking the sum of all multishuffles of multiwords of w α and w β , and finally translating each term back into a term Lγ by identifying the composition of the descent set. See [START_REF] Lam | Combinatorial Hopf algebras and K-homology of grassmannians[END_REF] for details. Note that there are infinitely many terms in the product of any two basis elements. For example, L(2,1) L(1) = L(2,2) + L(2,1,1) + L(3,1) + L(12121) + . . ., where the terms shown correspond to multishuffles 2314, 2431, 2341, 4243141 of w α = 231 and w β = 4.

Define the coproduct using the cuut coproduct of a word w:

(w 1 w 2 • • • w k ) = ∅ ⊗ w 1 • • • w k + w 1 ⊗ w 1 • • • w k + w 1 ⊗ w 2 • • • w k + w 1 w 2 ⊗ w 2 • • • w k + . . . + w 1 • • • w k ⊗ w k + w 1 • • • w k ⊗ ∅. Then let ∆( Lα ) = u⊗u in cuut(wα) LC(u) ⊗ LC(u ) .
For example,

∆( L(2,1) ) = ∅⊗ L(2,1) + L(1) ⊗ L(2,1) + L(1) ⊗ L(1,1) + L(2) ⊗ L(1,1) + L(2) ⊗ L(1) + L(2,1) ⊗ L(1) + L(2,1) ⊗∅ since (231) = ∅ ⊗ 231 + 2 ⊗ 231 + 2 ⊗ 31 + 23 ⊗ 31 + 23 ⊗ 1 + 231 ⊗ 1 + 231 ⊗ ∅.
Taking A to be mQSym with the basis { Lα } indexed by compositions, we create a dual filtered graph by taking f = L(1) and D = ξ • ∆ with g = L(1) . The first five ranks are shown below. This is a dual filtered graph by Theorem 3.3.

The following proposition shows that we have another instance of Möbius via Pieri phenomenon, just like in the case of Young's lattice.

Proposition 5.1 The Pieri construction above is a Möbius deformation of the dual graded graph composed of the lifted binary tree and BinWord in Section 5.1. The coproduct is similarly defined by taking the sum of the coproduct, ∆(w

K-Poirer-Reutenauer Peiri deformation

1 • • • w k ) = ∅ ⊗ w 1 • • • w k + std(w 1 ) ⊗ std(w 2 • • • w k ) + . . . + std(w 1 • • • w k-1 w k ) + std(w 1 • • • w k ) ⊗ ∅,
of each element in the class and writing the result as a sum of classes. Here, std(w) sends w to the unique word with the same relative order using all letters {1, 2, . . . , n} for some n. For example, std(13375) = 12243. Using this, we compute,

∆([[12]]) = [[∅]] ⊗ [[12]] + [[1]] ⊗ [[1]] + [[1]] ⊗ [[12]] + [[12]] ⊗ [[1]] + [[12]] ⊗ [[∅]].
Letting g = [[1]] and f = [[1]], we create a Pieri construction using Theorem 3.3. The partial dual filtered graph is shown below. The first five ranks are shown completely, and there are a few additional elements shown in the graph on the right to illustrate all elements that cover [212]. To see that there is an upward edge from [[3412]] to [[3124]], we first notice that 34124 ∈ [[3124]] and that 3412 ⊗ 1 appears in the coproduct of 34124.

In the figure below, K-Knuth equivalence classes of words are represented by an increasing tableau. Note that there may be more than one increasing tableau in any given class.

Let f λ be the number of increasing tabeleaux of shape λ. Let g λ n be the number of set-valued tableaux of shape λ and content 1, . . . , n. Let F (n) denote the Fubini number, or ordered Bell number -the number of ordered set partitions of This is the analogue of the famous Frobenius-Young identity. Of course, this also follows from bijectivity of Hecke insertion. The advantage of our proof is that a similar result exists for any dual filtered graph.

The following result is analogous to counting oscillating tableaux.

Theorem 6.3 For any dual graded graph the coefficient of ∅ in (D + U ) n (∅) is equal to the number of set partitions of [n] with parts of size at least 2.

  For example, in Young's lattice shown above, U (21) = 31 + 22 + 211 and D(21) = 2 + 11.

  Theorem 3.1 For any dual graded graph G, the trivial construction gives a dual filtered graph G .Example 3.2 The trivial construction for the first four ranks of Young's lattice is shown below. The edges in the graph on the left are oriented upward, and the edges in the graph on the right are oriented downward.

Lemma 3. 4

 4 The map D(a) = ξ(∆(a)) is a derivation.

  The Pieri deformation of Young's lattice is a dual filtered graph.

  combinatorial proof involving counting inner and outer corners, one can quickly show that [λ](DU -U D)µ = [λ]Dµ when µ covers λ, which suffices to prove the following result. Theorem 4.3 The Möbius deformation of Young's lattice forms a dual filtered graph.

Take

  A to be the K-theoretic Poierier-Reuntenauer bialgebra (KPR) defined inPatrias and Pylyavskyy (2014a) with a basis of K-Knuth classes of initial words (i.e. words containing only 1, 2, . . . , n for some n) on N. The K-Knuth relations are as follows: pqs ≡ qps and spq ≡ sqp for p < s < qSee[START_REF] Buch | k-theory of miniscule varieties[END_REF] for details on this relation. Multiplication of two classes [w 1 ] and [w 2 ] is done by shuffling each pair of elements, one from [w 1 ] and one from [w 2[n]], where w 1 is a word on n and w 2 [n] is obtained by adding n to each letter in w 2 , and writing the result as a sum of classes. For example,[[12]] • [[312]] = [[53124]] + [[51234]] +[[35124]] +[[351234]] +[[53412]] +[[5351234]].

  [n].Corollary 6.2 We have |λ|≤n f λ g λ n = F (n).

Acknowledgements

We thank Vic Reiner, Alexander Garver, and Thomas Lam for helpful discussions.

supported by NSF grant DMS-1148634. P.P. was supported by NSF grants DMS-1068169, DMS-1148634, DMS-1351590, and Sloan Fellowship. 1365-8050