A q-weighted version of the Robinson-Schensted algorithm

Abstract

We introduce a q-weighted version of the Robinson-Schensted (column insertion) algorithm which is closely connected to q-Whittaker functions (or Macdonald polynomials with t=0) and reduces to the usual Robinson-Schensted algorithm when q=0. The q-insertion algorithm is `randomised', or `quantum', in the sense that when inserting a positive integer into a tableau, the output is a distribution of weights on a particular set of tableaux which includes the output which would have been obtained via the usual column insertion algorithm. There is also a notion of recording tableau in this setting. We show that the distribution of weights of the pair of tableaux obtained when one applies the q-insertion algorithm to a random word or permutation takes a particularly simple form and is closely related to q-Whittaker functions. In the case $0\le q<1$, the q-insertion algorithm applied to a random word also provides a new framework for solving the q-TASEP interacting particle system introduced (in the language of q-bosons) by Sasamoto and Wadati (1998) and yields formulas which are equivalent to some of those recently obtained by Borodin and Corwin (2011) via a stochastic evolution on discrete Gelfand-Tsetlin patterns (or semistandard tableaux) which is coupled to the q-TASEP process. We show that the sequence of P-tableaux obtained when one applies the q-insertion algorithm to a random word defines another, quite different, evolution on semistandard tableaux which is also coupled to the q-TASEP process.

References in corpus (4)

• From duality to determinants for q-TASEP and ASEP
• Geometric RSK correspondence, Whittaker functions and symmetrized random polymers
• Littelmann paths and brownian paths
• A quantum algorithm for the quantum Schur-Weyl transform

Cited by in corpus (16)

• Spectral theory for the q-Boson particle system
• Macdonald processes, quantum integrable systems and the Kardar-Parisi-Zhang universality class
• Half-space Macdonald processes
• Generalizations of TASEP in discrete and continuous inhomogeneous space
• Notes on Schubert, Grothendieck and Key Polynomials
• The q-PushASEP: A New Integrable Model for Traffic in 1+1 Dimension
• Geometric RSK and the Toda lattice
• RSK in last passage percolation: a unified approach
• Law of Large Numbers for Infinite Random Matrices over a Finite Field
• A symmetry property for q-weighted Robinson-Schensted algorithms and other branching insertion algorithms
• Discrete time q-TASEPs
• Skew RSK dynamics: Greene invariants, affine crystals and applications to $q$-Whittaker polynomials
• A $q$-Robinson-Schensted-Knuth Algorithm and a $q$-polymer
• $q\mathrm{RS}t$: A probabilistic Robinson--Schensted correspondence for Macdonald polynomials
• $q\mathrm{RS}t$: A probabilistic Robinson--Schensted correspondence for Macdonald polynomials (extended abstract)
• q-Whittaker functions, finite fields, and Jordan forms