MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is a geometric construction of the dual RSK correspondence along the lines of Viennot's "light and shadows construction" written up somewhere? This is a bijective correspondence between 0-1 matrices and pairs of SSYT with mutually transpose shapes.

share|cite|improve this question

As far as I know, the Viennot's construction only works for RS algorithm taking permutations as input. For matrices there's a generalised version called matrix-ball construction, which can be found in 4.2 of "Young Tableaux" by William Fulton. I am not sure whether there is a matrix-ball construction for dual RSK algorithm.

However, if only consider permutations, then by replacing "row" to "column" in the description of RSK algorithm we get dual RSK algorithm. That means, the two tableaux obtained by dual RSK are exactly transposes of the pair by RSK, from the same permutation. Therefore the "light and shadow" construction still works for dual RSK and all one needs to do is place the readings to the columns rather than rows.

Edit: There is a matrix-ball construction for so-called Burge correspondence, see appendix A.4.1 of Fulton's book. Burge correspondence allows a non-negative integer matrix input for column insertion algorithm (by reading the matrix entries from right to left and top to bottom). This covers the case of words and permutations where each row only has one non-zero entry. I don't know the 0-1 matrix case yet. However, the description of matrix-ball construction is a bit too concise here for me to understand, especially how a new matrix of balls is constructed from an old one.

share|cite|improve this answer
True, the matrix ball construction generalizes the RS algorithm to RSK, but it seems no similar generalization is available for the dual RSK. – Amritanshu Prasad Feb 11 '13 at 5:37
up vote 3 down vote accepted

It's all written up rather nicely in Heather Dornom's Honours thesis from 2005. She gives a version of the matrix ball construction that works in these cases and also explains growth models for the RSK correspondence and its dual.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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