RS to RSK correspondence

Question

The RS correspondence is a correspondence which associates to each permutation a pair of standard Young tableaux of the same shape.

The RSK correspondence associates to each integer matrix (with non-negative entries) a pair of semistandard Young tableaux of the same shape.

Given an integer matrix, replace it by a permutation matrix whose rows and columns, when partitioned according to the row and column sums of the original matrix, have block sums equal to the entries of the original matrix. There is a unique such permutation matrix with the property that there are no descents within any of the blocks (each block is a partial permutation).

For example, if

$A=\begin{pmatrix} 2 & 1\\ 1 & 0\end{pmatrix}$

then the corresponding permutation matrix is

$\tilde A =\begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}$

Here the row and column partitions are both $(3,1)$.

It seems to be well-known (for example, it is implicit in Fulton's matrix ball construction) that to obtain the SSYT's for $A$, one may substitute for each entry in the SYT's for $\tilde A$ the integers corresponding to the blocks the rows and columns corresponding to these entries belong.

In the above example, the SYT's associated to $\tilde A$ are

$P = Q = \begin{array}{cc} 1 & 2 & 3 \\ 4 & &\end{array}$

into which we would saubstitute $1$ for $1,2,3$ and $2$ for $4$ to get the SSYT's for $A$:

$P = Q = \begin{array}{cc} 1 & 1 & 1 \\ 2 & & \end{array}$.

Is there a nice reference for this result?

Answer 1

I would look at chapter 7 in Enumerative Combinatorics, Volume 2, by Richard Stanley. A second place that can also be helpful for getting a good understanding of RS is Bruce Sagan's book called The Symmetric Group.

Answer 2

[Responding particularly to Bruce...] You may want to take a look at my thesis, which was the first place that the Knuth versions of RSK were "Fominized". There are lots of examples, which others have told me they've found helpful in understanding this material. (I'm sure Fomin already understood that this could be done, but it doesn't appear in his papers before 1991.) I put a scan on the web at:

http://www.math.uconn.edu/~troby/research.html

Scroll down to:

Applications and Extensions of Fomin's Generalization of the Robinson-Schensted Correspondence to Differential Posets, Ph.D. Thesis, Massachusetts Institute of Technology, 1991.

The key idea is just that RS commutes with "standardization" of words or SSYT, where one adds subscripts from Left to Right in the word and corresponding tableaux. See EC2, Lemma 7.11.6.

Thanks to Tricia Hersh for mentioning this thread at the SIAM DM conference. This is my first posting to MathOverflow, so I'm not allowed to comment.

Hope this helps!

Tom

Answer 3

Warning: I do not know nothing about combinatorial problems, so what I say now might be completely wrong. However: Rota in his talk at the Birkhoff memorial conference (The many lives of lattice theory, easily available online) has, in the section about semiprimary lattices, something which seemes strongly related.

Edit: citing from the article: each of the two chains is associated with a standard Young tableau, hence we obtain the statement and proof of the Schensted algorithm, which precisely associates a pair of standard Young tableaux to every permutation.