Generalization's of Greene's Theorem for the Robinson-Schensted correspondence

Question

One important property of the 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 (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 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.

Answer 1

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":

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, see also this paper by Thomas Lam)

Answer 2

For shifted RSK, see Section 3.5 of the thesis of Luis Guillermo Serrano Herrera at http://deepblue.lib.umich.edu/bitstream/handle/2027.42/77864/lserrano_1.pdf;jsessionid=B5A8F5AD166B6960A30EE5E16394A963?sequence=1.

Answer 3

Recent work by Patrias and Pylyavskyy introduces an analogue of dual graded graphs, which they call dual filtered graphs (see here). These allow for a dual graded graph-style characterization of Hecke insertion, as well as two novel insertion algorithms: shifted Hecke insertion and an Hecke insertion-type analogue of Young-Fibonacci insertion (which has a Greene's invariant studied by Fomin).

For insertion algorithms arising from dual filtered graphs, I suspect one can construct some appropriate analogue of a Greene's invariant, but do not see how to do so immediately.

Answer 4

There is a Greene-Kleitman invariant for the Hillman-Grassl correspondence; see Theorem 3.3 of Gansner's paper "The Hillman-Grassl correspondence and the enumeration of reverse plane partitions" (https://www.sciencedirect.com/science/article/pii/0097316581900418). See also Section 6 of Garver, Patrias, and Thomas's paper "Minuscule reverse plane partitions via quiver representations" (https://arxiv.org/abs/1812.08345), which explains how the Greene-Kleitman invariants for RSK and for the Hillman-Grassl correspondences can be seen "in the same way."