Abstract
We introduce and study q-randomized Robinson-Schensted-Knuth (RSK) correspondences which interpolate between the classical (q = 0) and geometric (q (Symbol found) 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 of Borodin-Corwin [8]). 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 studied by Borodin-Corwin [7] arise as onedimensional marginals of our “column” dynamics. In a similar way, our “row” dynamics lead to discrete time q-PushTASEPs-newintegrable particle systems in theKardar-Parisi-Zhang universality class. We employ these new one-dimensional discrete time systems to establish a Fredholmdeterminantal formula for the two-sided continuous time q-PushASEP conjectured by Corwin-Petrov [23]. (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 [59] and Borodin-Petrov [15], respectively. (3) In a scaling limit as q (Symbol found) 1, two of our four dynamics on interlacing arrays turn into the geometric RSK correspondences associated with log-Gamma (introduced by Seppäläinen [70]) or strict-weak (introduced independently by O’Connell-Ortmann [58] and Corwin-Seppäläinen-Shen [25]) directed random lattice polymers.
| Original language | American English |
|---|---|
| Pages (from-to) | 1-123 |
| Number of pages | 123 |
| Journal | Annales de l'Institut Henri Poincare (D) Combinatorics, Physics and their Interactions |
| Volume | 4 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2017 |
| Externally published | Yes |
ASJC Scopus subject areas
- Statistical and Nonlinear Physics
- Algebra and Number Theory
- Statistics and Probability
- Geometry and Topology
- Discrete Mathematics and Combinatorics
Keywords
- Interlacing particle arrays
- Macdonald processes
- Random partitions
- Random polymers
- Randomized insertion algorithm
- Robinson-Schensted-Knuth correspondence
- q-TASEP