Famous Robinson Schensted Knuth correspondence gives a correspondence between the matrices with non-negative integer entries and pair of semi standard tableaux. The proof that I have seen is highly combinatorial e.g. in Knuth's paper [Permutations, matrices, and generalized young tableaux]. Does there exist a geometrical proof of this correspondence?
$\begingroup$
$\endgroup$
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
2
This depends on the meaning of the word "geometric". If you are thinking of RSK and want the geometry in the way the algorithm is presented (in the case of permutations only), Viennot's paper Une forme geometrique de la correspondance de Robinson–Schensted mentioned by PeterR is your answer. If you are thinking of geometry of flag varieties, you might like Steinberg's theorem (see van Leeuwen's thesis A Robinson–Schensted algorithm in the geometry of flags for Classical Groups and his J. Algebra paper An Application of Hopf Algebra techniques to Representations of Finite Classical Groups. Finally, if you want RSK to be a map between integer points in polytopes, there are several versions of that, going back to Gansner in 1981 (you can find a description of that and references in the second half of the paper Hook length formula and geometric combinatorics of mine).
-
$\begingroup$ Thanks a lot for references. Let me look at these and find out, if I get the answer of what I am looking for. $\endgroup$ Commented Jul 8, 2010 at 5:21
-
1$\begingroup$ Note that there's now an open access link to Steinberg's 1988 paper: sciencedirect.com/science/article/pii/0021869388901779 $\endgroup$ Commented Sep 18, 2015 at 19:05
$\begingroup$
$\endgroup$
2
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.
answered Mar 2, 2012 at 12:40
-
$\begingroup$ You speak of "Fomin's growth-diagram approach (which can be given for the full RSK correspondence, even though it is often presented for permutations only).". Is there a good way to extend growth diagrams to the non-standard case without the (rather artificial IMHO) concept of standardization? $\endgroup$ Commented Mar 23, 2013 at 16:13
-
4$\begingroup$ @darij grinberg: For the Knuth correspondence, since the matrix can have entries larger than one, the "growth" of shapes can correspondingly be by more than one square; the natural condition is growth by horizontal strips. The original reference is S. Fomin, “Schur operators and Knuth correspondences”, J. Combin. Theory, Ser. A 72,(1995), pp. 277–292, though I might unmodestly suggest that my discussion in section 2.2 of "Spin-preserving Knuth correspondences for ribbon tableaux" combinatorics.org/Volume_12/Abstracts/v12i1r10.html is maybe more accessible (you can skip section 1). $\endgroup$ Commented Mar 26, 2013 at 13:30
$\begingroup$
$\endgroup$
Do you just want a proof that some bijection exists, or do you want a proof that the RSK bijection itself is a bijection? If the former, this is equivalent to the Cauchy identity in the theory of symmetric functions, for which many proofs have been given. For instance, it is equivalent to decomposing the symmetric algebra of $V\otimes W$ (where $V$ and $W$ are finite-dimensional complex vector spaces) into irreducible representations of $\operatorname{GL}(V)\times \operatorname{GL}(W)$, for which a direct argument is possible.
answered Jul 7, 2010 at 21:08
$\begingroup$
$\endgroup$
There is a generalization of Viennot's "ombres" mentioned in some of the other answers, called the matrix-ball construction, and which realizes the full RSK correspondence.
It is presented in Fulton's book "Young tableaux: with applications to representation theory and geometry", and as far as I remember was devised by Fulton itself.
answered Jul 9, 2010 at 17:01
$\begingroup$
$\endgroup$
Not involved approach to RSK is in Danilov, V. I.; Koshevoy, G. A. The octahedron recurrence and RSK-correspondence. Sém. Lothar. Combin. 54A (2005/07), Art. B54An, 16 pp. (electronic)
$\begingroup$
$\endgroup$
0
See "Une forme geometrique de la correspondance de Robinson–Schensted" by Viennot if you can read French. Otherwise, if I recall correctly it is in Sagan's book on the symmetric group.
