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.

  • $\begingroup$ The boycott be thanked, there is no paywall on Advances in Mathematics anymore. It's a good question, and I wouldn't be surprised if the straightforward RSK analogue (interpret the matrix of nonnegative integers as a "poset", with $k$ elements in every cell filled with integer $k$) would work as soon as one would sort out the failure of antisymmetry in these "posets". $\endgroup$ Mar 15 '13 at 17:44
  • 3
    $\begingroup$ I think the article of Haiman that you are thinking of is "Dual equivalence with applications, including a conjecture of Proctor", sciencedirect.com/science/article/pii/0012365X9290368P $\endgroup$ Mar 15 '13 at 17:48
  • $\begingroup$ We considered trying to construct Greene invariants for Hecke insertion but everything we tried turned out to be trivial. This is likely because the Hecke inserted tableaux, while uniquely determined, may be K-Knuth equivalent to other tableaux of different shape. $\endgroup$ Sep 5 '15 at 21:33
  • $\begingroup$ @MattSamuel Interesting. Have you looked at Patrias and Pylyavskyy (arxiv.org/abs/1410.7683)? $\endgroup$ Sep 5 '15 at 21:38
  • $\begingroup$ Yes. I'm the Samuel in citation 7! $\endgroup$ Sep 5 '15 at 22:50

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.


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)

  • $\begingroup$ If nothing else, you will be able to say something about the shape of the words in that article. $\endgroup$ Mar 16 '13 at 14:03
  • $\begingroup$ Sorry, I don't understand? $\endgroup$ Mar 16 '13 at 15:39
  • $\begingroup$ I would be very interested in why this answer was downvoted. Could you please leave a comment? Thanks. $\endgroup$ Mar 16 '13 at 15:49

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.


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.

  • $\begingroup$ What would a Greene invariant for increasing tableaux measure? The tableau may not have a unique shape. See my paper (Buch and Samuel) or Thomas and Yong's K-theory papers for examples. $\endgroup$ Sep 5 '15 at 23:14
  • $\begingroup$ (Side note; I believe Patrias et al have a more recent related paper.) $\endgroup$ Sep 5 '15 at 23:35

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.