8
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Alexander Woo
    Commented May 25, 2012 at 5:45
  • 1
    $\begingroup$ @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. $\endgroup$
    – Gjergji Zaimi
    Commented May 25, 2012 at 6:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bruce Westbury
    Commented May 25, 2012 at 9:06

2 Answers 2

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks! The word tropical seems to be used in a funny way here (doesn't it usually go the other way around?). $\endgroup$
    – Gjergji Zaimi
    Commented May 25, 2012 at 19:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented May 25, 2012 at 23:48
  • $\begingroup$ @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. $\endgroup$
    – Roger Van Peski
    Commented Jan 30, 2019 at 18:14
3
$\begingroup$

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

MR1872253 (2003j:05128)
Kirillov, Anatol N.
Introduction to tropical combinatorics.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .