[Math] Geometric proof of Robinson-Schensted-Knuth correspondence

co.combinatoricsrobinson-schensted-knuthrt.representation-theory

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?

Best Answer

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).

Related Solutions

[Math] Definition of infinite permutations

There are two closely related definitions which satisfy the properties you want.

First, consider the group $\Sigma_k$ of all bijections $\pi: \Bbb Z \to \Bbb Z$ such that $\pi(x+k) = \pi(x)+k$ for all $x$. Note that $S_k$ is a subgroup in $\Sigma_k$ - simply take any permutation of $\{1,\ldots,k\}$ and extend it periodically to all $x$. This group (introduced by Lusztig) is finitely generated and is closely related to affine Lie algebra $\widehat A_k$. The RSK algorithm does not exactly work here, but Lusztig does study the shape of Young diagrams (of what would be resulting two tableaux). The shape is a partition of $k$, and can be described using decreasing subsequences, extending Curtis Greene's theorem (I forgot if this is in Lusztig's paper or my own easy observation).

Second, a somewhat related definition is the group $\Phi_k$ of bijections $\pi: \Bbb N \to \Bbb N$ such that $\pi(x+k) = \pi(x)+k$ for all $x$ large enough. I studied this definition in this paper. This group $\Phi_k$ is also finitely generated. It is very suitable for RSK, which is not always, but sometimes invertible. The asymptotic shape I defined is essentially the same as Lusztig's. Neither I nor anyone else studied the infinite matrix extension. The infinite permutation version is already difficult enough.

[Math] Implementation of the Robinson-Schensted Correspondence

It doesn't require linked lists, just arrays that can grow.

There's a Java applet online that implements it.

I'm sure there are other implementations online, but since I couldn't find any, as a start, here's a simple Python implementation. [Though it feels odd giving a programming answer here, and I'm sure several people here can write it much better!]

from bisect import bisect
def RSK(p):
    '''Given a permutation p, spit out a pair of Young tableaux'''
    P = []; Q = []
    def insert(m, n=0):
        '''Insert m into P, then place n in Q at the same place'''
        for r in range(len(P)):
            if m > P[r][-1]:
                P[r].append(m); Q[r].append(n)
                return
            c = bisect(P[r], m)
            P[r][c],m = m,P[r][c]
        P.append([m])
        Q.append([n])

    for i in range(len(p)):
        insert(int(p[i]), i+1)
    return (P,Q)

print RSK('1364752')

Edit: Used binary search to improve from O(n³) to O(n²log n), which should matter only for very large permutations.

Best Answer

Related Solutions

[Math] Definition of infinite permutations

[Math] Implementation of the Robinson-Schensted Correspondence

Related Question