A q-weighted version of the Robinson-Schensted algorithm

DOI10.1214/EJP.V18-2930zbMATH Open1278.05243arXiv1212.6716OpenAlexW2952528239MaRDI QIDQ388991FDOQ388991

Authors: Neil O'Connell, Yuchen Pei 

Publication date: 17 January 2014

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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 $0leq<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.

Full work available at URL: https://arxiv.org/abs/1212.6716

Recommendations

• A symmetry property for \(q\)-weighted Robinson-Schensted and other branching insertion algorithms
• A \(q\)-Robinson-Schensted-Knuth algorithm and a \(q\)-polymer
• The Robinson-Schensted and Schützenberger algorithms, an elementary approach
• scientific article; zbMATH DE number 17892
• A Robinson-Schensted algorithm for a class of partial orders
• A \(q\)-analog of approximation inclusion-exclusion
• A q-difference version of the ϵ-algorithm
• A relation for domino Robinson-Schensted algorithms
• Robinson-Schensted algorithm and Vogan equivalence
• Graph-Theoretic Concepts in Computer Science

zbMATH Keywords

Macdonald polynomials\(q\)-Whittaker functions

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Symmetric functions and generalizations (05E05) Interacting particle systems in time-dependent statistical mechanics (82C22)

Cited In (24)

• Nearest neighbor Markov dynamics on Macdonald processes
• A \(q\)-deformation of the symplectic Schur functions and the Berele insertion algorithm
• Some algebraic structures in KPZ universality
• Completeness of the Bethe ansatz for an open \(q\)-Boson system with integrable boundary interactions
• Spectral theory for interacting particle systems solvable by coordinate Bethe ansatz
• Notes on Schubert, Grothendieck and key polynomials
• Anisotropic \((2+1)\)d growth and Gaussian limits of \(q\)-Whittaker processes
• A probabilistic interpretation of the Gaussian binomial coefficients
• Hall-Littlewood RSK field
• Generalizations of TASEP in discrete and continuous inhomogeneous space
• RSK in last passage percolation: a unified approach
• The \(q\)-PushASEP: a New Integrable Model for Traffic in \(1+1\) dimension
• A \(q\)-Robinson-Schensted-Knuth algorithm and a \(q\)-polymer
• Half-space Macdonald processes
• Law of large numbers for infinite random matrices over a finite field
• Stochastic higher spin six vertex model and \(q\)-TASEPs
• Yang-Baxter random fields and stochastic vertex models
• Skew RSK dynamics: Greene invariants, affine crystals and applications toq-Whittaker polynomials
• PushTASEP in inhomogeneous space
• \(q\)-Whittaker functions, finite fields, and Jordan forms
• qRSt: a probabilistic Robinson-Schensted correspondence for Macdonald polynomials
• \(q\)-randomized Robinson-Schensted-Knuth correspondences and random polymers
• A symmetry property for \(q\)-weighted Robinson-Schensted and other branching insertion algorithms
• Yang-Baxter field for spin Hall-Littlewood symmetric functions

This page was built for publication: A \(q\)-weighted version of the Robinson-Schensted algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q388991)