q-randomized Robinson-Schensted-Knuth correspondences and random polymers
2015/04/01
Konstantin Matveev, Leonid PetrovAnnales de l'Institut Henri Poincare D: Combinatorics, Physics and their Interactions 4 (2017), no. 1, 1-123 • arXiv:1504.00666 [math.PR]
We introduce and study $q$-randomized Robinson-Schensted-Knuth (RSK) correspondences which interpolate between the classical ($q=0$) and geometric ($q\to 1$) RSK correspondences (the latter ones are sometimes also called tropical).
For $0< q <1$ our correspondences are randomized, i.e., the result of an insertion is a certain probability distribution on semistandard Young tableaux. Because of this randomness, we use the language of discrete time Markov dynamics on two-dimensional interlacing particle arrays (these arrays are in a natural bijection with semistandard tableaux). Our dynamics act nicely on a certain class of probability measures on arrays, namely, on $q$-Whittaker processes (which are $t=0$ versions of Macdonald processes). We present four Markov dynamics which for $q=0$ reduce to the classical row or column RSK correspondences applied to a random input matrix with independent geometric or Bernoulli entries.
Our new two-dimensional discrete time dynamics generalize and extend several known constructions: (1) The discrete time $q$-TASEPs arise as one-dimensional marginals of our “column” dynamics. In a similar way, our “row” dynamics lead to discrete time $q$-PushTASEPs - new integrable particle systems in the Kardar-Parisi-Zhang universality class. We employ these new one-dimensional discrete time systems to establish a Fredholm determinantal formula for the two-sided continuous time $q$-PushASEP conjectured by Corwin-Petrov (2013). (2) In a certain Poisson-type limit (from discrete to continuous time), our two-dimensional dynamics reduce to the $q$-randomized column and row Robinson-Schensted correspondences introduced by O'Connell-Pei (2012) and Borodin-Petrov (2013), respectively. (3) In a scaling limit as $q\to1$, two of our four dynamics on interlacing arrays turn into the geometric RSK correspondences associated with log-Gamma or strict-weak directed random polymers.
A q-deformation of the Robinson-Schensted-Knuth algorithm