One important property of the [Robinson-Schensted correspondence](http://en.wikipedia.org/wiki/Robinson-Schensted_correspondence) (RS) is that the longest increasing subsequence of the permutation $\sigma$ is $\lambda\_1$, the first entry of the shape $\lambda(\sigma)$ of the tableaux associated to $\sigma$. [Greene's theorem](http://www.sciencedirect.com/science/article/pii/0001870874900310) (sorry for the paywall) generalizes this result to $k$-increasing sequences and the sum $\lambda\_1 + \dots + \lambda\_k$.


Are there generalizations of Greene's theorem to other insertion algorithms? Such algorithms would include RSK, Hecke insertion, Edelman-Greene insertion and any other variants you are aware of. In particular, it seems a generalization of this is known for the full [RSK](http://en.wikipedia.org/wiki/Robinson-Schensted-Knuth_correspondence) correspondence, but I am having difficulty finding a reference. Moreover, I was told of an article by Haiman on generalizations of RS that may include such results, but have never found it.



Generalization's of Greene's Theorem for the Robinson-Schensted correspondence
For RSK the answer is "well known". You can find the statements neatly arranged in an article by Christian Krattenthaler <http://arxiv.org/abs/math/0510676>.


I think the right framework for this question is Sergey Fomin's theory of dual graded graphs.
However, I don't think there are many other insertion algorithms where the Greene-Kleitman invariant is known. One is the insertion algorithm for shifted tableaux, and another, easy one is the pair (BinTree, BinWord).


In fact, whenever you have such a Greene-Kleitman invariant and whenever this invariant behaves well with respect to "promotion", you are in a good position to get a result parallel to <http://arxiv.org/abs/math/0604140>. For the pair (BinTree, BinWord) this is indeed the case (and interesting), but I never managed to write it up due to time constraints...


For Edelman-Greene the story is slightly different I think. If I recall correctly you can say at least a little bit about the shape of the word by staring long enough at the article by Christian Stump and Luis Serrano <http://arxiv.org/abs/1009.4690> or myself <http://arxiv.org/abs/1009.3919>.


EDIT:


The Kleitman Greene invariants for some insertion algorithms (**for the standard case**, i.e., where the words are permutations) are described in Sergey Fomin's paper ["Schensted algorithms for dual graded graphs"](ftp://192.43.228.178/pub/EMIS/journals/JACO/Volume4_1/j3330612tm0w1m47.fulltext.pdf):


1) Theorem 4.4.4: Young-Fibonacci insertion (due to Tom Roby and Sergey Fomin, perhaps the invariant for Janvier Nzeutchap's algorithm is different).


2) Just below Proposition 4.5.2: Shifted insertion (attributed to Worley and Bruce Sagan, see Richard Stanley's answer for the description in the semistandard case due to Luis Serrano)


3) Proposition 4.6.2: (BinTree, BinWord)-insertion (independently due to Xavier Viennot)


I'd be interested in learning about Kleitman-Greene invariants for other insertion algorithms. In particular, is it known for domino insertion (as described by [Marc van Leeuwen](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r15), see also [this paper](http://arxiv.org/abs/math/0308265) by Thomas Lam)


