Combinatorial Dynamics: From Patience Sorting to the Discrete-Time Toda Lattice
Tropicalisation provides a mechanism for relating combinatorial/algorithmic processes to dynamic/integrable ones, often of a stochastic character. One of the classical examples of this was the algorithmic (in terms of "patience sorting") determination of the asymptotic expected value of the longest increasing sequence in a permutation which is related to a Poissonised process that can be effectively analysed by integrable methods of Riemann-Hilbert analysis. However, in this example, the nature of the underlying dynamics is somewhat obscured. A model of great current interest (which in fact generalises the patience sorting example) starts with the Robinson-Schensted-Knuth (RSK) algorithm and relates it by a "tropical" correspondence to the dynamics of the discrete Toda lattice. The novelty and aim of our approach is to provide deeper insight into all of this in terms of factorisations of one-dimensional discrete Schrödinger-type operators and related Bäcklund transformations, with the focus of this talk being on the latter.