Connection between various RS(K) algorithms and directed last passage percolation / directed polymer models

greene_theorem robinson_schensted robinson_schensted_knuth

The various RS(K) algorithms are connected to various DLPP / DP models, through Greene's theorems or local dynamics. Basically, the first row of the output tableau (or equivalently the first edge of the Gelfand-Tsetlin pattern) evolves in the same way as DLPP / DP model. One may equivalently say that the DLPP / DP are the RS(K) algorithms restricted to the first row of tableau / edge of GT pattern.

Example. the \((\lambda^m_j(n))_{jmn}\) be the output GT patterns of the usual RSK algorithm taking matrix \(A = (a_{ij})\). And recall the notation \(Z_0(n, m)\) in discrete_dlpp_dp. One can show that \((\lambda^m_1(n))_{mn}\) satisfies the same global ((1) in discrete_dlpp_dp) and local ((3) in discrete_dlpp_dp) formulas that define \((Z_0(m, n))_{mn}\).

Using the same arguments, we establish the following correspondence:

• The \((\lambda^m_1(n))\) of the output GT patterns of the \(q\)RSK algorithm are the same as the \(q\)DLPP. (Note this can be only shown by identification of the local formula as there is no global formula for \(q\)DLPP, see the open problem in discrete_dlpp_dp.
• The \((\lambda^m_1(n))\) of the output GT patterns of the gRSK algorithm are the same as the directed polymer.
• The \((\lambda^m_1(n))\) of the output GT patterns of the Pitman's transform of type A are the same as the semi-discrete percolation.
• The \((\lambda^m_1(n))\) of the output GT patterns of geometric lifting of the Pitman's transform are the same as the semi-discrete / O'Connell-Yor polymer.