Printer Friendly

The shifted plactic monoid (extended abstract).

[...] pour affirmer la necessite d'installer le monolde plaxique parmi les structures remarquables.

--M.-P. Schutzenberger (16)

Introduction

The (shifted) plactic monoid. The celebrated Robinson-Schensted-Knuth correspondence (14) is abijection between words in a linearly ordered alphabet X = {1 < 2 < 3 < ...} and pairs of Young tableaux with entries in X. More precisely, each word corresponds to a pair consisting of a semistandard insertion tableau and a standard recording tableau. The words producing a given insertion tableau form a plactic class. A. Lascoux and M. P. Schutzenberger (11) made a crucial observation based on a result by D. E. Knuth (6): the plactic classes [u] and [v] of two words u and v uniquely determine the plactic class [uv] of their concatenation. This gives the set of all plactic classes (equivalently, the set of all semistandard Young tableaux) the structure of a plactic monoid P = P(X). This monoid has important applications in representation theory and the theory of symmetric functions; see, e.g., (10).

The main goal of this paper is to construct and study a proper analog of the plactic monoid for (semistandard) shifted Young tableaux, with similar properties and similar applications. The problem of developing such a theory was already posed more than 20 years ago by B. Sagan (12). Shifted Young tableaux are certain fillings of a shifted shape (a shifted Young diagram associated with a strict partition) with letters in an alphabet X' = {1' < 1 < 2' < 2 < ...}; see, e.g., (13). M. Haiman (5) defined the (shifted) mixed insertion correspondence, a beautiful bijection between permutations and pairs of standard shifted Young tableaux; each pair consists of the mixed insertion tableau and the mixed recording tableau. Haiman's correspondence is easily generalized to a bijection between words in the alphabet X and pairs consisting of a semistandard shifted mixed insertion tableau and a standard shifted mixed recording tableau. (We emphasize that this bijection deals with words in the original alphabet X rather than the extended alphabet X'.) We define a shifted plactic class as the set of all words which have a given mixed insertion tableau. Thus, shifted plactic classes are in bijection with shifted semistandard Young tableaux. The following key property, analogous to that of Lascoux and Schutzenberger's in the ordinary case, holds (Theorem 4): the shifted plactic class of the concatenation of two words u and v depends only on the shifted plactic classes of u and v. Consequently, one can define the shifted plactic monoid S = S(X) in which the product is, again, given by concatenation. In analogy with the classical case, we obtain a presentation of S by the quartic shifted Knuth (or shifted plactic) relations. So two words are shifted Knuth-equivalent if and only if they have the same mixed insertion tableau.

Sagan (12) and Worley (20) have introduced the Sagan-Worley correspondence, another analog of Robinson-Schensted-Knuth correspondence for shifted tableaux. In the case of permutations, Haiman (5) proved that the mixed insertion correspondence is dual to Sagan-Worley's. We use a semistandard version of this duality to describe shifted plactic equivalence in yet another way, namely: two words u and v are shifted plactic equivalent if and only if the recording tableaux of their inverses (as biwords) are the same.

(Shifted) Plactic Schur functions. The plactic algebra QP is the semigroup algebra of the plactic monoid. The shape of a plactic class is the shape of the corresponding tableau. A plactic Schur function [S.sub.[lambda]] [member of] QP is the sum of all plactic classes of shape [lambda]; it can be viewed as a noncommutative version of the ordinary Schur function [s.sub.[lambda]]. This notion was used by Schutzenberger (15) to obtain a proof of the Littlewood-Richardson rule along the following lines. It can be shown that the plactic Schur functions span the ring they generate. Furthermore, this ring is canonically isomorphic to the ordinary ring of symmetric functions: the isomorphism simply sends each Schur function [s.sub.[lambda]] to its plactic counterpart [S.sub.[lambda]]. It follows that the Littlewood-Richardson coefficient [c.sup.[lambda].sub.[mu],v] is equal to the coefficient of a fixed plactic class [T.sub.[lambda]] of shape [lambda] in the product of plactic Schur functions [S.sub.[mu]][S.sub.v]. In other words, is equal to the number of pairs ([T.sub.[mu]], [T.sub.v]) of plactic classes of shapes [mu] and v such that [T.sub.[mu]][T.sub.v] = [T.sub.[lambda]].

We develop a shifted counterpart of this classical theory. The shifted plactic algebra QS is the semigroup algebra of the shifted plactic monoid, and a (shifted) plactic Schur P-function [P.sub.[lambda]] [member of] QS is the sum of all shifted plactic classes of a given shifted shape. We prove that the plactic Schur P- functions span the ring they generate, and this ring is canonically isomorphic to the ring spanned/generated by the ordinary Schur P-functions. Again, the isomorphism sends each Schur P-function [P.sub.[lambda]] to its plactic counterpart [P.sub.[lambda]]. This leads to a proof of the shifted Littlewood-Richardson rule (Corollary 16). Our version of the rule states that the coefficient [b.sup.[lambda].sub.[mu],v] of [P.sub.[lambda]] in the product [P.sub.[mu]][P.sub.v] is equal to the number of pairs ([T.sub.[mu]], [T.sub.v]) of shifted plactic classes of shapes [mu] and v such that [T.sub.[mu]][T.sub.v] = [T.[lambda]], where [T.sub.[lambda]] is a fixed shifted plactic class of shape [lambda]. The first version of the shifted Littlewood-Richardson rule was given by Stembridge (19). In Lemma 18 we relate our rule to Stembridge's by a simple bijection.

It turns out that the shifted plactic relations are a "relaxation" of the ordinary Knuth (plactic) relations.

More precisely, the tautological map u [??] u that sends each word in the alphabet X to itself descends to a monoid homomorphism S [right arrow] P. By extending this map linearly, we obtain the following theorem (Corollary 21): For a shifted shape [theta], the coefficient [g.sup.[theta].sub.[mu]] of [s.sub.[mu]] in the Schur expansion of [P.sub.[theta]] is equal to the number of shifted plactic classes of shifted shape [theta] contained in a fixed plactic class of shape [mu]. A simple bijection (Theorem 23) recovers a theorem of Stembridge (19): [g.sup.[theta].sub.[mu]] is equal to the number of standard Young tableaux of shape [mu] which rectify to a fixed standard shifted Young tableau of shape [theta].

(Shifted) Tableau words. In the classical setting, an approach developed by Lascoux and his school begins with the plactic monoid as the original fundamental object, and identifies each tableau T with a distinguished canonical representative of the corresponding plactic class, the reading word read(T). This word is obtained by reading the rows of T from left to right, starting from the bottom row and moving up. A word w such that w = read(T) for some tableau T is called a tableau word. By construction, tableau words are characterized by the following property. Each of them is a concatenation of weakly increasing words w = [u.sub.l][u.sub.l-1] ... [u.sub.1], such that

(A) for 1 [less than or equal to] i [less than or equal to] l - 1, the longest weakly increasing subword of [u.sub.i+1][u.sub.i] is [u.sub.i].

For a tableau word w, the lengths of the segments [u.sub.i] are precisely the row lengths of the Young tableau corresponding to w.

We develop an analog of this approach in the shifted setting by taking the shifted plactic monoid as the fundamental object, and constructing a canonical representative for each shifted plactic class. Since shifted Young tableaux have primed entries while the words in their respective shifted plactic classes have not, the reading of a shifted Young tableau cannot be defined in as simple a manner as in the classical case. Instead, we define the mixed reading word mread(T) of a shifted tableau T as the unique word in the corresponding shifted plactic class that has a distinguished special recording tableau. The latter notion is a shifted counterpart of P. Edelman and C. Greene's dual reading tableau (1).

A word w such that w = mread(T) for some shifted Young tableau T is called a shifted tableau word. Such words have a characterizing property similar to (A), with weakly increasing words replaced by hook words (a hook word consists of a strictly decreasing segment followed by a weakly increasing one). We prove that w is a shifted tableau word if and only if

(B) for 1 [less than or equal to] i [less than or equal to] l - 1, the longest hook subword of [u.sub.i+1][u.sub.i] is [u.sub.4].

For a shifted tableau word w, the lengths of the segments [u.sub.i] are precisely the row lengths of the shifted Young tableau corresponding to w.

Semistandard decomposition tableaux. The proofs of our main results make use of the following machinery. Building on the concept of standard decomposition tableaux introduced by W. Kraskiewicz (7) and further developed by T. K. Lam (9), we define a (shifted) semistandard decomposition tableau (SSDT) R of shifted shape [lambda] as a filling of A by entries in X such that the rows [u.sub.1], [u.sub.2], ..., [u.sub.l] of R are hook words satisfying (B). We define the reading word of R by read(R) = [u.sub.l][u.sub.l-1] ... [u.sub.1], that is, by reading the rows of R from left to right, starting with the bottom row and moving up.

As a semistandard analog of Kraskiewicz's correspondence (7), we develop the SK correspondence. This is a bijection between words in the alphabet X and pairs of tableaux with entries in X. Every word corresponds to a pair consisting of an SSDT called the SK insertion tableau and a standard shifted Young tableau called the SK recording tableau. We prove that the mixed recording tableau and the SK recording tableau of a word w are the same. Furthemore, we construct a bijection [PHI] between SSDT and shifted Young tableaux of the same shape that preserves the reading word: read(R) = mread([PHI](R)). In light of the conditions (A) and (B) above, one can see that the counterpart of an SSDT in the ordinary case is nothing but a semistandard Young tableau.

This text is an extended abstract of the preprint (17), where complete proofs can be found.

Main results

Preliminaries: shifted Young tableaux and the mixed insertion

A strict partition is a sequence [lambda] = ([[lambda].sub.1]; [[lambda].sub.2], ..., [[lambda].sub.l];) [member of] [Z.sup.l] such that [[lambda].sub.1] > [[lambda].sub.2] > ... > [[lambda].sub.l] > 0. The shifted diagram, or shifted shape of [lambda] is an array of square cells in which the i-th row has [[lambda].sub.i] cells, and is shifted i - 1 units to the right with respect to the top row.

Throughout this paper, we identify a shifted shape corresponding to a strict partition [lambda] with [lambda] itself.

The size of [lambda] is [absolute value of [lambda]] = [[lambda].sub.1] + [[lambda].sub.2] + ... + [[lambda].sub.l]. We denote l([lambda]) = l, the number of rows.

To illustrate, the shifted shape [lambda] = (5, 3, 2), with [absolute value of [lambda]] = 10 and l([lambda]) = 3, is shown below:

[ILLUSTRATION OMITTED]

A skew shifted diagram (or shape) [lambda]/[mu] is obtained by removing a shifted shape [mu] from a larger shape [lambda] containing [mu].

A (semistandard) shifted Young tableaux T of shape [lambda] is a filling of a shifted shape [lambda] with letters from the alphabet X' = {1' < 1 < 2' < 2 < ...} such that:

* rows and columns of T are weakly increasing;

* each k appears at most once in every column;

* each k' appears at most once in every row;

* there are no primed entries on the main diagonal.

If T is a filling of a shape A, we write shape(T) = [lambda].

A skew shifted Young tableau is defined analogously.

The content of a tableau T is the vector ([a.sub.1], [a.sub.2], ...), where [a.sub.i] is the number of times the letters i and i' appear in T.

Example 1 The shifted Young tableau

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

has shape [lambda] = (5, 3, 2) and content (2, 1, 1, 2, 2, 1, 0, 0, 1).

A tableau T of shape [lambda] is called standard if it contains each of the entries 1,2, ..., [absolute value of [lambda]] exactly once. In particular, standard shifted Young tableaux have no primed entries. Note that a standard shifted tableau has content (1, 1, ..., 1).

M. Haiman (5) has introduced shifted mixed insertion, a remarkable correspondence between permutations and pairs of shifted Young tableaux. Haiman's construction can be viewed as a shifted analog of the Robinson-Schensted-Knuth correspondence.

The following is a semistandard generalization of shifted mixed insertion, which we call semistandard shifted mixed insertion. It is a correspondence between words in the alphabet X and pairs of shifted Young tableaux, one of them semistandard and one standard. Throughout this paper we refer to semistandard shifted mixed insertion simply as mixed insertion.

Definition 2 (Mixed insertion) Let w = [w.sub.1] ... [w.sub.n] be a word in the alphabet X. We recursively construct a sequence ([T.sub.0], [U.sub.0]), ..., ([T.sub.n], [U.sub.n]) = (T,U) of tableaux, where [T.sub.i] is a shifted Young tableau, and [U.sub.i] is a standard shifted Young tableau, as follows. Set ([T.sub.0], [U.sub.0]) = (0,0). For i = 1, ..., n, insert [w.sub.i] into [T.sub.i-1] in the following manner:

Insert [w.sub.i] into the first row, bumping out the smallest element a that is strictly greater than [w.sub.i] (in the order given by the alphabet X').

1. if a is not on the main diagonal, do as follows:

(a) if a is unprimed, then insert it in the next row, using step (1);

(b) if a is primed, insert it into the next column to the right, using the same procedure as in row insertion;

2. if a is on the main diagonal, then it must be unprimed. Prime it, and insert it into the next column to the right.

The insertion process terminates once a letter is placed at the end of a row or column, bumping no new element. The resulting tableau is [T.sub.i].

The shapes of [T.sub.i-1] and [T.sub.i] differ by one box. Add that box to [U.sub.i-1], and write i into it to obtain [U.sub.i].

We call T the mixed insertion tableau and U the mixed recording tableau, and denote them [P.sub.mix](w) and [Q.sub.mix](w), respectively.

Example 3 The word u = 3415961254 has the following mixed insertion and recording tableau

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The shifted plactic monoid

The following is a shifted analog of Knuth's Theorem (6). It can be considered a semistandard generalization of theorems by Haiman (5) and by Krasskiewicz (7).

Theorem 4 Two words u and v have the same mixed insertion tableau if and only if they are equivalent modulo the following relations:

abdc [equivalent to] adbc for a [less than or equal to] b [less than or equal to] c < d in X; (1)

acdb [equivalent to] acbd for a [less than or equal to] b < c [less than or equal to] d in X; (2)

dacb [equivalent to] adcb for a [less than or equal to] b < c [less than or equal to] d in X; (3)

badc [equivalent to] bdac for a < b [less than or equal to] c < d in X; (4)

cbda [equivalent to] cdba for a < b < c [less than or equal to] d in X; (5)

dbca [equivalent to] bdca for a < b [less than or equal to] c < d in X; (6)

bcda [equivalent to] bcad for a < b [less than or equal to] c [less than or equal to] d in X; (7)

cadb [equivalent to] cdab for a [less than or equal to] b < c [less than or equal to] d in X. (8)

See Remark 7 for a concise alternative description of relations (1)-(8).

Definition 5 Two words u and v in the alphabet X are shifted plactic equivalent, denoted u [equivalent to] v, if they have the same mixed insertion tableau. By Theorem 4, u and v are shifted plactic equivalent if they are equivalent modulo the shifted plactic relations (1)-(8).

A shifted plactic class is an equivalence class under [equivalent to]. We can associate a shifted plactic class with its corresponding shifted Young tableau, or with any of the words in the class, which insert to the corresponding tableau. The shifted plactic class corresponding to the Young tableau T is denoted [T], and the shifted plactic class that contains a word u is denoted [u]. The Appendix at the end of (17) shows all kinds of shifted plactic classes of 4-letter words.

For a word w = [w.sub.1][w.sub.2] ... [w.sub.n] in X, let [P.sub.RSK] (w) be its Robinson- Schensted-Knuth insertion tableau. Two words u and v in the alphabet X are plactic equivalent if [P.sub.RSK](u) = [P.sub.RSK](v). Knuth (6) has proved that the latter holds if and only if u and v are equivalent modulo the plactic relations

acb ~ cab for a [less than or equal to] b < c in X, (9)

bca ~ bac for a < b [less than or equal to] c in X. (10)

Remark 6 (cf. (16)) Relations (9)-(10) can be restated as follows. Let us call w a line word if

[w.sub.1] > [w.sub.2] > ... > [w.sub.n]

or

[w.sub.1] [less than or equal to] [w.sub.2] [less than or equal to] ... [less than or equal to] [w.sub.n].

Line words are precisely those words w for which the shape of [P.sub.RSK](w) is a single row or a single column.

Two 3-letter words w and w' in the alphabet X are plactic equivalent if and only if:

* w and w' differ by an adjacent transposition, and

* neither w nor w' is a line word.

Remark 7 The shifted plactic relations can be described in a similar way. Define a hook word as a word w = [w.sub.1] ... [w.sub.l] such that for some 1 [less than or equal to] k [less than or equal to] Z, we have

[w.sub.1] > [w.sub.2] > ... > [w.sub.k] [less than or equal to] [w.sub.k+1] [less than or equal to] ... [less than or equal to] [w.sub.l]. (11)

It is easy to see that w is a hook word if and only if [P.sub.mix](w) consists of a single row.

Two 4-letter words w and w' in the alphabet X are shifted plactic equivalent if and only if:

* w and w' are plactic equivalent, and

* neither w nor w' is a hook word.

The following proposition can be verified by direct inspection.

Proposition 8 Shifted plactic equivalence is a refinement of plactic equivalence. That is, each plactic class is a disjoint union of shifted plactic classes. To put it yet in another way: if two words are shifted plactic equivalent, then they are plactic equivalent.

For 4-letter words, Proposition 8 is illustrated in the Appendix to (17).

Definition 9 The shifted plactic monoid is the set of shifted plactic classes where multiplication is given by [u][v] = [uv]. Equivalently, the monoid is generated by the symbols in X subject to the relations (1)-(8).

An alternative point of view is to identify the shifted plactic classes with the corresponding shifted Young tableaux, thus giving a notion of a (shifted plactic) product of shifted tableaux.

The shape of a shifted plactic class is defined as the shape of the corresponding shifted Young tableau.

The shifted plactic algebra QS is the semigroup algebra of the plactic monoid.

Example 10 One can check that both words in each of the shifted plactic relations have the same mixed insertion tableau. For example, for relation (1),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 11 The words u = 3415961254 and v = 3451196524 are shifted Knuth equivalent, because [P.sub.mix](u) = [P.sub.mix](v). (cf. Example 3.) Furthermore, one can obtain v from u by the following a sequence of shifted plactic relations (where the relation to be used is stated and highlighted in bold)

u = 3415961254 (1)

= 3415961524 (3)

= 3415916524 (3)

= 3415196524 (7)

= 3451196524

= v.

Plactic Schur P-functions and their applications

For a shifted Young tableau T, with content ([a.sub.1], [a.sub.2], ...) define its corresponding monomial as [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For each strict partition [lambda], the Schur P-function is defined as the generating function for shifted Young tableaux of shape [lambda], namely

[P.sub.[lambda]] = [P.sub.[lambda]]([x.sub.1], [x.sub.2], ...) = [summation over (shape(T)=[lambda])] [x.sup.T].

The Schur Q-function is given by

[Q.sub.[lambda]] = [Q.sub.[lambda]] ([x.sub.1], [x.sub.2], ...) = [2.sup.l([lambda]) [P.sub.[lambda],

or equivalently, as the generating function for a different kind of shifted Young tableaux, namely those in which the elements in the main diagonal are allowed to be primed

The skew Schur P- and Q-functions [P.sub.[lambda]/[mu]] and [Q.sub.[lambda]/[mu]] = [2.sup.l([lambda])-l([mu])] [P.sub.[lambda]/[mu]] are defined similarly, on a skew shifted shape [lambda][mu].

The following is an example of a Schur P-function in two variables:

Example 12 For [lambda] = (3,1),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The Schur P- and Q-Schur functions form bases for an important subring [OMEGA] of the ring [LAMBDA] of symmetric functions.

The shifted Littlewood-Richardson coefficients, [b.sup.[lambda].sub.[mu],v] are of great importance in combinatorics, algebraic geometry, and representation theory. They appear in the expansion of the product of two Schur P-functions,

[P.sub.[mu]][P.sub.v] = [summation over ([lambda])] [b.sup.[lambda].sub.[mu],v][P.sub.[lambda]]

and also in the expansion of a skew Schur Q-function

[Q.sub.[lambda]/[mu]] = [summation over (v)][b.sup.[lambda].sub.[mu],v][Q.sub.v].

The latter can be rewritten as

[P.sub.[lambda]/[mu]] = [summation over (v)] [2.sup.l([mu])+l(v)- l([lambda])][b.sup.[lambda].sub.[mu],v][P.sub.v].

Definition 13 A shifted plactic Schur P-function [P.sub.[lambda]] [member of] QS is defined as the sum of all shifted plactic classes of shape [lambda]. More specifically,

[P.sub.[lambda]] = [summation over (shape(T)=[lambda])] [T].

Example 14 We represent each shifted plactic class as [w], for some representative w, to obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The reader can check that each word gets mixed inserted into the tableau underneath, making it a valid representative of its corresponding plactic class.

One can see that the [P.sub.[lambda]] are noncommutative analogs of the Schur P-functions. In the last example, P(3,1) is the noncommutative analog of

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

Theorem 15 The map [P.sub.[lambda]] [??] [P.sub.[lambda]] extends to a canonical isomorphism between the algebra generated by the ordinary and shifted plactic Schur P-functions, respectively. As a result, the [P.sub.[lambda]] commute pairwise, span the ring they generate, and multiply according to the shifted Littlewood-Richardson rule. Namely,

[P.sub.[mu]][P.sub.v] = [[summation over ([lambda])] [b.sup.[lambda].sub.[mu],v] [P.sub.[lambda]]. (13)

Sagan (12) has extended the concept of jeu de taquin to shifted tableaux, and proved that, just as in the ordinary case, the result of applying a sequence of (shifted) jeu de taquin moves is independent from the order in which they are done. Throughout this paper we only apply shifted jeu de taquin to standard skew tableaux, for which the process is exactly as it is done in the ordinary case. For pairs of standard skew tableaux T and U, we say that T rectifies to U if U can be obtained from T by a sequence of shifted jeu de taquin moves.

Our first application of Theorem 15 is a new proof (and a new version of) the shifted Littlewood- Richardson rule. Stembridge (19) proved that the shifted Littlewood-Richardson number [b.sup.[lambda].sub.[mu],v] is equal to the number of standard shifted Young skew tableaux of shape [lambda]/[mu] which rectify to a fixed standard shifted Young tableau of shape v.

By taking the coefficient of the shifted plactic class [T] corresponding to a fixed tableau T of shape [lambda] on both sides of (13), one obtains the following:

Corollary 16 (Shifted Littlewood-Richardson rule) Fix a shifted plactic class [T] of shape [lambda]. The shifted Littlewood-Richardson coefficient [b.sup.[lambda].sub.[mu],v] is equal to the number of pairs of shifted plactic classes [U] and [V] of shapes [mu] and v, respectively, such that [U][V] = [T].

Remark 17 This rule can be restated in the language of words as follows. In Chapter 2 of (17) we introduce a canonical representative ofthe shifted plactic class [T] corresponding to the tableau T. This representative is called the mixed reading word of T, and denoted mread(T). A word w is called a shifted tableau word if w = mread(T) for some shifted Young tableau T. The shape of a shifted tableau word is given by the shape of the corresponding tableau.

With this terminology, the shifted Littlewood-Richardson rule can be restated as follows: Fix a shifted tableau word w of shape [lambda]. The shifted Littlewood-Richardson coefficient [b.sup.[lambda].sub.[mu],v] is equal to the number of pairs of shifted tableau words u, v of shapes [mu], v, respectively, such that w [equivalent to] uv.

Lemma 18 Fix a shifted tableau word w of shape [lambda] and fix a standard shifted tableau Q of shape v. The number of pairs of shifted tableau words u, v of shapes [mu] and v, respectively, such that uv = w is equal to the number of standard shifted skew tableaux of shape [lambda]/[mu] which rectify to Q.

As a corollary, we obtain the original result of Stembridge (19).

Corollary 19 Fix a standard shifted tableau Q of shape v. The coefficient [b.sup.[lambda].sub.[mu],v] is equal to the number of standard shifted skew tableaux of shape [lambda]/[mu] which rectify to Q.

Example 20 We compute [b.sup.21.sub.2,1] = 1. For this, we fix the shifted tableau word w = 132, associated to the shifted Young tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The only way to express w = uv where u and v are reading words of shapes (2) and (1), respectively, is with u = 13, associated to the tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and v = 2, associated to the tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The second application is a new proof (and a new version of) the Schur expansion of a Schur P - function. Stembridge (19) has found a combinatorial interpretation for the coefficient [g.sup.[theta].sub.[mu]] in the sum

[P.sub.[theta]] = [[summation over ([mu])] [9.sup.[theta].sub.[mu]][s.sub.[mu]].

We find a different interpretation for the [9.sup.[theta].sub.[mu]] in terms of shifted plactic classes. Lascoux and Schutzenberger (11) have defined the plactic monoid P as follows. Two words are plactic equivalent if they have the same Robinson-Schensted-Knuth insertion tableau. A plactic class is an equivalence class under plactic equivalence. The plactic class of a word u in the alphabet X is denoted &lt;u&gt;. P is the set of plactic classes where multiplication is given by &lt;u&gt;<v> = <uv>. Equivalently, it is generated by the symbols in X subject to the Knuth relations (9)-(10).

Recall, by Proposition 8, any two shifted plactic equivalent words are plactic equivalent, or in other words, plactic classes decompose into a union of shifted plactic classes. This yields the natural projection

[pi] : S [right arrow] P,

in which the shifted plactic class [u] gets mapped to the plactic class &lt;u&gt;.

We now consider the image of a plactic Schur P-function under [pi].

Theorem 21 The plactic Schur P-function [P.sub.[theta]] gets mapped under [pi] to a sum of plactic Schur functions [S.sub.[mu]]. The coefficients [9.sup.[theta].sub.[mu]] are the same as those in

[pi]([P.sub.[theta]] = [summation over ([mu])] [9.sup.[theta].sub.[mu]][S.sub.[mu]].

Moreover, [9.sup.[theta].sub.[mu]] is equal to the number of shifted plactic classes [u] of shifted shape [theta] such that [pi]([u]) = <v> for some fixed plactic class (v) of shape [mu].

Example 22 Let [mu] be the ordinary shape (3,1), and [theta] be the shifted shape (3,1). We compute the coefficient [g.sup.[theta].sub.[mu]] = 1; this is the coefficient of [s.sub.[mu]] in [P.sub.[theta]] (cf. (12)). For this, we fix &lt;u&gt; = <2134>, namely, the plactic class corresponding to the Young tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that the words in &lt;u&gt; are 2134, 2314, and 2341. These get split into two shifted plactic classes, namely [2134] corresponding to the shifted Young tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and [2314] = [2341] corresponding to the shifted Young tableau [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since the only one of these plactic classes has shape [mu], namely <2314>, we get [9.sup.[theta].sub.[mu]] = 1.

Theorem 23 Let [theta] be a shifted shape, and [U.sub.[theta]] a fixed standard shifted tableau of shape [theta]. Fix a plactic class <[T.sub.[mu]]> of shape Let [G.sup.[theta].sub.[mu]] be the set of shifted plactic classes [[T.sub.[theta]]] of shape theta for which [pi]([[T.sub.[theta]]]) = ([T.sub.[mu]]). Let [H.sup.[theta].sub.[mu]] be the set of standard Young tableaux of shape [mu] which rectify to [U.sub.[theta]]. Then the sets [G.sup.[theta].sub.[mu]] and [H.sup.[theta].sub.[mu]] are in bijection.

As a corollary, we obtain the original result of Stembridge (19).

Corollary 24 The coefficient [g.sup.[theta].sub.[mu]] is equal to the number of standard Young tableaux [Q.sub.[mu]] of shape [mu] which rectify to a fixed standard shifted Young tableau [Q.sub.[theta]] of shape [theta].

For ordinary Young tableau, one uses the concept of rectification (under jeu de taquin) to obtain the Littlewood-Richardson coefficients in the Schur expansion of a skew Schur function.

We have been unable to construct an analog of a jeu de taquin slide for skew semistandard shifted tableaux, but nonetheless, we can define the rectification rect(T) of such a tableau T; see (17, Section 2.1). (In the notation of (17, Lemma 2.11), rect(T) = [P.sub.mix](mread(T)).) We then define the shifted plactic skew Schur P-function of shape [lambda]/[mu] as the following element of QS:

[P.sub.[lambda]/v] = [summation over (shape(T)=[lambda]/[mu])] [rect(T)].

Conjecture 25 [P.sub.[lambda]/[mu]] belongs to the ring generated by the plactic Schur P-functions.

Corollary 26 Fix a shifted Young tableau U of shape v. The coefficient of [P.sub.v] in [P.sub.[lambda]/[mu]] is equal to the number of skew shifted Young tableauxT with rect(T) = U.

Remark 27 For the moment we can prove a slightly weaker statement than Conjecture 25. The projection [pi]([P.sub.[lambda]/[mu]]) (which lives in QP) belongs to the ring generated by the plactic Schur functions [S.sub.[mu]]. This will enable us to find a combinatorial interpretation for the coefficients in the Schur expansion of the skew Schur P-functions.

Acknowledgements I am grateful to Sergey Fomin for suggesting the problem and for his comments on the earlier versions of the paper. I would also like to thank Marcelo Aguiar, Curtis Greene, Tadeusz Jozefiak, Alain Lascoux, Thomas Lam, Cedric Lecouvey, Pavlo Pylyavskyy, Bruce Sagan, John Stembridge, and Alex Yong for helpful and inspiring conversations.

References

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

[2] S. Fomin and C. Greene, Noncommutative Schur functions and their applications, Discrete Math. 193 (1998), 179-200.

[3] C. Greene, An extension of Schensted's theorem, Adv. Math. 14 (1974), 254-265.

[4] M. D. Haiman, Dual equivalence with applications, including a conjecture of Proctor, Discrete Math 99 (1992), 79-113.

[5] M. D. Haiman, On mixed insertion, symmetry, and shifted young tableaux, J. Combin. Theory Ser. A 50 (1989), 196-225.

[6] D. E. Knuth, Permutations, matrices, and generalized Young tableaux Pacific J. Math. 34 (1970), 709-727.

[7] W. Kraskiewicz, Reduced decompositions in hyperoctahedral groups, C. R. Acad. Sci. Paris Str. I Math. 309 (1989), 903-907.

[8] T. K. Lam, B and D analogues of stable Schubert polynomials and related insertion algorithms, Ph.D. thesis, MIT, 1994; available at http://hdl.handle.net/1721.l736537.

[9] T. K. Lam, Bn Stanley symmetric functions. Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ, 1994). Discrete Math. 157 (1996), 241-270.

[10] A. Lascoux, B. Leclerc, J. -Y. Thibon, The plactic monoid, in "M. Lothaire, Algebraic combinatorics on words", Cambridge University Press, Cambridge, 2002 (Chapter 6).

[11] A. Lascoux and M.-P. Schutzenberger, Le monoide plaxique, Quaderni de 'La ricerca scientifica 109 (1981), 129-156.

[12] B. Sagan, Shifted tableaux, Schur Q-functions, and a conjecture of R. P. Stanley, J. Combin. Theory Ser. A 45 (1987), 62-103.

[13] B. Sagan, The ubiquitous Young tableau, in: Invariant theory and Young tableaux, D. Stanton (ed.), Springer-Verlag (1990), 262-298.

[14] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961), 179- 191.

[15] M.P. Schutzenberger, La correspondence de Robinson, Combinatorie et Representation du Groupe Symetrique (D. Foata ed.), Lecture Notes in Math. 579 (1977), 59-135.

[16] M.P. Schutzenberger, Pour le monoide plaxique, Math. Inform. Sci. Humaines 140 (1997), 5-10.

[17] L. Serrano, The shifted plactic monoid; available at http://arxiv.org/abs/0811.2057.

[18] R. Stanley, Enumerative Combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, UK, 1999.

[19] J. Stembridge, Shifted Tableaux and the Projective Representations of Symmetric Groups, Adv. in Math. 74 (1989), 87-134.

[20] D. R. Worley, A theory of shifted Young tableaux, Ph.D. thesis, MIT, 1984; available at http://hdl.handle.net/172L1/15599.

Luis Serrano ([dagger])

Department of Mathematics

University of Michigan, Ann Arbor, MI 48109, USA

lserrano@umich.edu

([dagger]) Partially supported by NSF grant DMS-0555880 and by an NSERC Postgraduate Scholarship.
COPYRIGHT 2009 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Serrano, Luis
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2009
Words:5818
Previous Article:Noncrossing partitions and the shard intersection order.
Next Article:[kappa]-parabolic subspace arrangements.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters