Viennot-type geometric description for dual RSK correspondence?

Question

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.

Answer 1

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.

Answer 2

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.