Analysis and Its Applications Seminar- Combinatorial Dynamics: From Patience Sorting to Discrete Schrödinger Operators

Abstract: Tropicalization 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 Poissonized process that can be effectively analyzed 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 generalizes 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 of our approach is to provide deeper insight into all this in terms of factorizations of discrete Schrödinger-type operators and related Bäcklund transformations.