RS to RSK correspondence - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T14:46:57Z http://mathoverflow.net/feeds/question/100085 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100085/rs-to-rsk-correspondence RS to RSK correspondence Amritanshu Prasad 2012-06-20T07:01:42Z 2012-06-22T12:29:35Z <p>The RS correspondence is a correspondence which associates to each permutation a pair of standard Young tableaux of the same shape.</p> <p>The RSK correspondence associates to each integer matrix (with non-negative entries) a pair of semistandard Young tableaux of the same shape.</p> <p>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).</p> <p>For example, if</p> <p><code>$A=\begin{pmatrix} 2 &amp; 1\\ 1 &amp; 0\end{pmatrix}$</code></p> <p>then the corresponding permutation matrix is </p> <p><code>$\tilde A =\begin{pmatrix} 1 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 1\\ 0 &amp; 0 &amp; 1 &amp; 0\end{pmatrix}$</code></p> <p>Here the row and column partitions are both $(3,1)$.</p> <p>It seems to be well-known (for example, it is implicit in Fulton's <em>matrix ball construction</em>) that to obtain the SSYT's for $A$, one may substitute for each entry in the SYT's for <code>$\tilde A$</code> the integers corresponding to the blocks the rows and columns corresponding to these entries belong.</p> <p>In the above example, the SYT's associated to $\tilde A$ are </p> <p><code>$P = Q = \begin{array}{cc} 1 &amp; 2 &amp; 3 \\ 4 &amp; &amp;\end{array}$</code></p> <p>into which we would saubstitute $1$ for $1,2,3$ and $2$ for $4$ to get the SSYT's for $A$:</p> <p><code>$P = Q = \begin{array}{cc} 1 &amp; 1 &amp; 1 \\ 2 &amp; &amp; \end{array}$</code>.</p> <p>Is there a nice reference for this result?</p> http://mathoverflow.net/questions/100085/rs-to-rsk-correspondence/100091#100091 Answer by NN for RS to RSK correspondence NN 2012-06-20T07:47:04Z 2012-06-22T12:29:35Z <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/100085/rs-to-rsk-correspondence/100092#100092 Answer by Patricia Hersh for RS to RSK correspondence Patricia Hersh 2012-06-20T07:59:24Z 2012-06-20T07:59:24Z <p>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. </p> http://mathoverflow.net/questions/100085/rs-to-rsk-correspondence/100134#100134 Answer by Tom Roby for RS to RSK correspondence Tom Roby 2012-06-20T13:37:43Z 2012-06-20T13:37:43Z <p>[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:</p> <p><a href="http://www.math.uconn.edu/~troby/research.html" rel="nofollow">http://www.math.uconn.edu/~troby/research.html</a></p> <p>Scroll down to: </p> <p>Applications and Extensions of Fomin's Generalization of the Robinson-Schensted Correspondence to Differential Posets, Ph.D. Thesis, Massachusetts Institute of Technology, 1991. </p> <p>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. </p> <p>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. </p> <p>Hope this helps!</p> <p>Tom</p>