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: