# What is the tropical Robinson-Schensted-Knuth correspondence?

And what are it's applications? A conceptual explanation would be great! Is there an expository note about this somewhere?

Some references have already appeared in the answers and comments below. To make the question more specific, classical RSK has combinatorial interpretations in terms of symmetric functions, for example. If RSK gives the Cauchy identity: $$\sum_{\lambda} s _{\lambda}(x)s _{\lambda}(y)=\prod _{i,j} \frac{1}{1-x_iy_j}$$ what is an analogous interpretation for tropical RSK? (From some buzzwords I've heard in a few talks recently, it probably has something to do with shifted or elliptic Schur functions.)

• Could you give some details on where you got the idea there would be such a thing in the first place? I know what 'tropical' means and what 'RSK' is, but don't know of a place where they are connected (though I could guess at least one). May 25, 2012 at 5:45
• @Alexander: Here is a recent paper talking about this: arxiv.org/abs/1110.3489 I have heard it mentioned in the context of some probability problems, and was wondering what it means combinatorially. I'm not so interested on the applications as much as on the bijections involved and it's relation to classical RSK. May 25, 2012 at 6:01
• I have heard Neil O'Connell talk on this. Unfortunately he spent most of the time on RSK and only touched on the tropical version. May 25, 2012 at 9:06

I think the clearest write up is in Danilov and Koshevoy. Let me try to get you off on the right foot by explaining what it is we are proving.

RSK (for these purposes) is a bijection between $n \times n$ nonnegative integer matrices and pairs of SSYT of the same shape, filled with entries from $1$ to $n$. By the bijection between SSYT and Gelfand-Tsetlin patterns, this is the same as pairs of GT-patterns of size $n$ with the same bottom row. Remember that a GT-pattern is a triangular array of numbers so, if we glue these two GT-patterns together along their common entries, we get a square.

Thus, we have encoded both sides of the RSK correspondence as $n \times n$ arrays of integers obeying certain inequalities. On one side, the inequality is that the entries are nonnegative, on the other side we have the GT inequalities. Then the key facts are the following:

1. This map is piece-wise linear.

2. As a piece-wise linear function, it is (once you get all the coordinates right) the tropicalization of the LU factorization map: The birational map which takes an $n \times n$ matrix and writes it as a product of a lower triangular and an upper triangular matrix.

• Thanks! The word tropical seems to be used in a funny way here (doesn't it usually go the other way around?). May 25, 2012 at 19:21
• Yes. The literature by Kirillov and his Japanese collaborators use the word "tropical" backwards from everyone else. Allen Knuston pointed out to me that their usage is more logical -- if you think about thermodynamics, then the discrete piecewise linear side should be the temperature zero limit. But it doesn't seem likely that this usage will be adopted by many others. May 25, 2012 at 23:48
• @DavidESpeyer is the interpretation in terms of LU decomposition which you mention present in Danilov and Koshevoy? I didn’t see it there but perhaps I just didn’t understand what was going on well enough. Jan 30, 2019 at 18:14

I believe this paper is the starting point for this topic:

MR1872253 (2003j:05128)
Kirillov, Anatol N.
Introduction to tropical combinatorics.