# q-randomized Robinson-Schensted-Knuth correspondences and random polymers

### 2015/04/01

Konstantin Matveev, Leonid Petrov

*Annales 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