Besides the original definition in terms of reduced words, the Stanley symmetric functions can be computed in at least three ways, which seem mysteriously different enough to me that it’s worth talking about all of them.
It turns out that in the Schur expansion , the coefficients are nonnegative integers, so it’s natural to ask for a combinatorial interpretation for them. Edelman and Greene gave a nice answer to this question. The column word of a semistandard tableau is the word gotten by reading up the first column, then the second column, and so on. Say is the set of semistandard tableaux whose column words are reduced words for . Then is the number of tableaux in with shape .
For example, , and each of these is the column word of exactly one tableau: and respectively, so . , but only the second of these can be the column word of a semistandard tableau, namely , so .
In fact Edelman-Greene do better than this. Previously I mentioned that the equality falls out of the definition of , where is the number of standard tableaux of shape . Given the interpretation of , this suggests there should be a bijection
Edelman-Greene provide just such a bijection. If you know the Robinson-Schensted(-Knuth) correspondence, this should look familiar—Edelman-Greene’s bijection is very similar, and includes Robinson-Schensted as the special case .
This also solves the problem of sampling uniformly from , as long as we can compute . For example, take the special case , where has just one element (because ). It turns out to be easy to uniformly choose a standard tableau of a particular shape (using the “hook walk” algorithm), so choose with the same shape as and apply the Edelman-Greene bijection to the pair to obtain a reduced word.
The Edelman-Greene bijection shows that the coefficients are nonnegative integers. Since the Schur functions are irreducible characters for (if is large enough), this means is the character of a -module. This module turns out to have a nice description not relying on knowing its decomposition into irreducibles.
Here’s how to get the module whose character is (called a Schur module). Start with the left -module , where . This is also a right -module, permutations acting by permuting tensor factors. Construct the Young symmetrizer , a member of the group algebra . Then the Schur module is .
The construction of the Young symmetrizer uses the Ferrers diagram of , but only actually relies on having a set of boxes to put numbers in, not that the boxes are arranged in any particular way. That is, any finite set has a Young symmetrizer using the same definition, and so there’s a -module .
The Stanley symmetric function turns out to be the character of one of these guys. The inversion set of a permutation is . Then is the character of . [I’m not sure who to credit this to… Kraśkiewicz and Pragacz? Let’s say yes, Poles unite!!]
is more or less the Ferrers diagram of , so we recover again that . The equality from this point of view ends up being the classic decomposition of 2-tensors into symmetric and antisymmetric parts, .
Schubert calculus, in modern terms, amounts to doing calculations in the cohomology ring of Grassmannians or flag varieties (or more generally, a semisimple algebraic group mod a parabolic subgroup). Take the subgroups of upper and lower triangular matrices, respectively, in . A (complete) flag in is a sequence of subspaces with . The collection of flags in is naturally in bijection with the flag variety , a projective variety.
The LU decomposition (or LPU) gives the Bruhat decomposition of : the disjoint union , interpreting as a permutation matrix. This descends to a decomposition . Each is a Schubert cell , homeomorphic to some ; the Schubert variety is the closure of . The Schubert cells form a CW decomposition of , and have even real dimensions, so the classes Poincaré dual to the Schubert varieties form a -basis of .
As for the ring structure, by realizing as the total space of the top of a tower of projective bundles over , one can compute that is a certain quotient of . Lots of classical enumerative geometry questions can be phrased in terms of counting intersection points between various Schubert varieties, so one should try to find polynomials representing the Schubert classes in this picture of .
Lascoux and Schützenberger found a nice set of such polynomials, the Schubert polynomials . They have the nice property of being stable under the inclusions , meaning that for , represents in whenever , if we view as a permutation of fixing .
Schubert polynomials enjoy another kind of stability. Write for the permutation . It turns out that as , converges to a power series in . This power series is exactly !