10
$\begingroup$

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.

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ True, the matrix ball construction generalizes the RS algorithm to RSK, but it seems no similar generalization is available for the dual RSK. $\endgroup$ Feb 11, 2013 at 5:37
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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