Return to Answer

This is more a comment on some of the answers given than an answer to the question itself (which isn't too clear in the first place: a correspondence is not something to prove, and why should one want a geometric proof of a statement (whichever) that is fundamentally combinatorial, unless it's just the right brain hemisphere that wants to join in the game?)

I have said this before, in print long ago, but since many people seem not to be aware I'll say it again: while a beautiful presentation, Viennot's description with shadows (ombres) is just a restatement of the "graph-theoretical viewpoint" that is given in Knuth's original paper (section 4), in a somewhat more geometric language. In fact I think the approach is really poset-theoretic: a permutation gives rise to a poset by embedding the $1$'s of permutation matrix into $\mathbb N^2$ with the product partial ordering. The graph that Knuth considers is basically the restricted partial ordering, viewed as a directed graph (there is a minor complication for general integer matrices instead of permutation matrices, as they give rise to points with multiplicity). Viennot's partition into shadows is just the partition of the poset into anti-chains according to the "height" of its elements: the length of the longest chain ending in the element (which description is given in the Knuth paper). Once the shadows are defined, the construction proceeds by iterative formation of derived (and ever smaller) subsets of $\mathbb N^2$/posets/digraphs in exactly the same way. Fulton's matrix-ball construction is again a reformulation of Viennot's construction, taking care to adapt to the general integer-matrix context of Knuth's paper; otherwise there is nothing new here either.

Personally I find the iterative nature of these constructions limit their transparency, even though it does not interfere with their proof of the symmetry of the RS / RSK correspondence. A similar "geometric" approach, but which really adds insight with respect to Knuth's paper is Fomin's growth-diagram approach (which can be given for the full RSK correspondence, even though it is often presented for permutations only). One has to consider all points of (the relevant part of) $\mathbb N^2$ rather than just those occurring in the poset, and one has to attach partitions to each of them according to a somewhat subtle rule, but then the construction produces in one swoop (without iteration) the full pair of tableaux.

This is more a comment on some of the answers given than an answer to the question itself (which isn't too clear in the first place: a correspondence is not something to prove, and why should one want a geometric proof of a statement (whichever) that is fundamentally combinatorial, unless it's just the right brain hemisphere that wants to join in the game?)

I have said this before, in print long ago, but since many people seem not to be aware I'll say it again: while a beautiful presentation, Viennot's description with shadows (ombres) is just a restatement of the "graph-theoretical viewpoint" that is given in Knuth's original paper Permutations, matrices, and generalized Young tableaux (section 4), in a somewhat more geometric language. In fact I think the approach is really poset-theoretic: a permutation gives rise to a poset by embedding the $1$'s of permutation matrix into $\mathbb N^2$ with the product partial ordering. The graph that Knuth considers is basically the restricted partial ordering, viewed as a directed graph (there is a minor complication for general integer matrices instead of permutation matrices, as they give rise to points with multiplicity). Viennot's partition into shadows is just the partition of the poset into anti-chains according to the "height" of its elements: the length of the longest chain ending in the element (which description is given in the Knuth paper). Once the shadows are defined, the construction proceeds by iterative formation of derived (and ever smaller) subsets of $\mathbb N^2$/posets/digraphs in exactly the same way. Fulton's matrix-ball construction is again a reformulation of Viennot's construction, taking care to adapt to the general integer-matrix context of Knuth's paper; otherwise there is nothing new here either.

Personally I find the iterative nature of these constructions limit their transparency, even though it does not interfere with their proof of the symmetry of the RS / RSK correspondence. A similar "geometric" approach, but which really adds insight with respect to Knuth's paper is Fomin's growth-diagram approach (which can be given for the full RSK correspondence, even though it is often presented for permutations only). One has to consider all points of (the relevant part of) $\mathbb N^2$ rather than just those occurring in the poset, and one has to attach partitions to each of them according to a somewhat subtle rule, but then the construction produces in one swoop (without iteration) the full pair of tableaux.

This is more a comment on some of the answers given than an answer to the question itself (which isn't too clear in the first place: a correspondence is not something to prove, and why should one want a geometric proof of a statement (whichever) that is fundamentally combinatorial, unless it's just the right brain hemisphere that wants to join in the game?)

I have said this before, in print long ago, but since many people seem not to be aware I'll say it again: while a beautiful presentation, Viennot's description with shadows (ombres) is just a restatement of the "graph-theoretical viewpoint" that is given in Knuth's original paper (section 4), in a somewhat more geometric language. In fact I think the approach is really poset-theoretic: a permutation gives rise to a poset by embedding the $1$'s of permutation matrix into $\mathbb N^2$ with the product partial ordering. The graph that Knuth considers is basically the restricted partial ordering, viewed as a directed graph (there is a minor complication for general integer matrices instead of permutation matrices, as they give rise to points with multiplicity). Viennot's partition into shadows is just the partition of the poset into anti-chains according to the "height" of its elements: the length of the longest chain ending in the element (which description is given in the Knuth paper). Once the shadows are defined, the construction proceeds by iterative formation of derived (and ever smaller) subsets of $\mathbb N^2$/posets/digraphs in exactly the same way. Fulton's matrix-ball construction is again a reformulation of Viennot's construction, taking care to adapt to the general integer-matrix context of Knuth's paper; otherwise there is nothing new here either.

Personally I find the iterative nature of these constructions limit their transparency, even though it does not interfere with their proof of the symmetry of the RS / RSK correspondence. A similar "geometric" approach, but which really adds insight with respect to Knuth's paper is Fomin's growth-diagram approach (which can be given for the full RSK correspondence, even though it is often presented for permutations only). One has to consider all points of (the relevant part of) $\mathbb N^2$ rather than just those occurring in the poset, and one has to attach partitions to each of them according to a somewhat subtle rule, but then the construction produces in one swoop (without iteration) the full pair of tableaux.

This is more a comment on some of the answers given than an answer to the question itself (which isn't too clear in the first place: a correspondence is not something to prove, and why should one want a geometric proof of a statement (whichever) that is fundamentally combinatorial, unless it's just the right brain hemisphere that wants to join in the game?)

I have said this before, in print long ago, but since many people seem not to be aware I'll say it again: while a beautiful presentation, Viennot's description with shadows (ombres) is just a restatement of the "graph-theoretical viewpoint" that is given in Knuth's original paper (section 4), in a somewhat more geometric language. In fact I think the approach is really poset-theoretic: a permutation gives rise to a poset by embedding the $1$'s of permutation matrix into $\mathbb N^2$ with the product partial ordering. The graph that Knuth considers is basically the restricted partial ordering, viewed as a directed graph (there is a minor complication for general integer matrices instead of permutation matrices, as they give rise to points with multiplicity). Viennot's partition into shadows is just the partition of the poset into anti-chains according to the "height" of its elements: the length of the longest chain ending in the element (which description is given in the Knuth paper). Once the shadows are defined, the construction proceeds by iterative formation of derived (and ever smaller) subsets of $\mathbb N^2$/posets/digraphs in exactly the same way. Fulton's matrix-ball construction is again a reformulation of Viennot's construction, taking care to adapt to the general integer-matrix context of Knuth's paper; otherwise there is nothing new here either.

Personally I find the iterative nature of these constructions limit their transparency, even though it does not interfere with their proof of the symmetry of the RS / RSK correspondence. A similar "geometric" approach, but which really adds insight with respect to Knuth's paper is Fomin's growth-diagram approach (which can be given for the full RSK correspondence, even though it is often presented for permutations only). One has to consider all points of (the relevant part of) $\mathbb N^2$ rather than just those occurring in the poset, and one has to attach partitions to each of them according to a somewhat subtle rule, but then the construction produces in one swoop (without iteration) the full pair of tableaux.

This is more a comment on some of the answers given than an answer to the question itself (which isn't too clear in the first place: a correspondence is not something to prove, and why should one want a geometric proof of a statement (whichever) that is fundamentally combinatorial, unless it's just the right brain hemisphere that wants to join in the game?)

I have said this before, in print long ago, but since many people seem not to be aware I'll say it again: while a beautiful presentation, Viennot's description with shadows (ombres) is just a restatement of the "graph-theoretical viewpoint" that is given in Knuth's original paper (section 4), in a somewhat more geometric language. In fact I think the approach is really poset-theoretic: a permutation gives rise to a poset by embedding the $1$'s of permutation matrix into $\mathbb N^2$ with the product partial ordering. The graph that Knuth considers is basically the restricted partial ordering, viewed as a directed graph (there is a minor complication for general integer matrices instead of permutation matrices, as thay give rise to points with multiplicity). Viennot's partition into shadows is just the partition of the poset into anti-chains according to the "height" of its elements: the length of the longest chain ending in the element (which descritpion is given in the Knuth paper). Once the shadows are defined, the construction proceeds by iterative formation of derived (and ever smaller) subsets of $\mathbb N^2$/posets/digraphs in exactly the same way. Fulton's matrix-ball construction is again a reformulation of Viennot's construction, taking care to adapt to the general integer-matrix context of Knuth's paper; otherwise there is nothing new here either.

Personally I find the iterative nature of these constructions limit their transparency, even though it does not interfere with their proof of the symmetry of the RS / RSK correspondence. A similar "geometric" approach, but which really adds insight with respect to Knuth's paper is Fomin's growth-diagram approach (which can be given for the full RSK correspondence, even though it is often presented for permutations only). One has to consider all squares of (the relevant part of) $\mathbb N^2$ rather than just those occurring in the poset, and one has to attach partitions to each of them according to a somewhat sublte rule, but then the construction produces in one swoop (without iteration) the full pair of tableaux.

This is more a comment on some of the answers given than an answer to the question itself (which isn't too clear in the first place: a correspondence is not something to prove, and why should one want a geometric proof of a statement (whichever) that is fundamentally combinatorial, unless it's just the right brain hemisphere that wants to join in the game?)

I have said this before, in print long ago, but since many people seem not to be aware I'll say it again: while a beautiful presentation, Viennot's description with shadows (ombres) is just a restatement of the "graph-theoretical viewpoint" that is given in Knuth's original paper (section 4), in a somewhat more geometric language. In fact I think the approach is really poset-theoretic: a permutation gives rise to a poset by embedding the $1$'s of permutation matrix into $\mathbb N^2$ with the product partial ordering. The graph that Knuth considers is basically the restricted partial ordering, viewed as a directed graph (there is a minor complication for general integer matrices instead of permutation matrices, as they give rise to points with multiplicity). Viennot's partition into shadows is just the partition of the poset into anti-chains according to the "height" of its elements: the length of the longest chain ending in the element (which description is given in the Knuth paper). Once the shadows are defined, the construction proceeds by iterative formation of derived (and ever smaller) subsets of $\mathbb N^2$/posets/digraphs in exactly the same way. Fulton's matrix-ball construction is again a reformulation of Viennot's construction, taking care to adapt to the general integer-matrix context of Knuth's paper; otherwise there is nothing new here either.

Personally I find the iterative nature of these constructions limit their transparency, even though it does not interfere with their proof of the symmetry of the RS / RSK correspondence. A similar "geometric" approach, but which really adds insight with respect to Knuth's paper is Fomin's growth-diagram approach (which can be given for the full RSK correspondence, even though it is often presented for permutations only). One has to consider all points of (the relevant part of) $\mathbb N^2$ rather than just those occurring in the poset, and one has to attach partitions to each of them according to a somewhat subtle rule, but then the construction produces in one swoop (without iteration) the full pair of tableaux.