A \(q\)-analog of the hook walk algorithm and random Young tableaux
type: Item
instance of: scholarly article
title: A \(q\)-analog of the hook walk algorithm and random Young tableaux
zbMATH Open document ID: 0796.05092
DOI: 10.1007/BF01075631
publication date: 1994-07-26T00:00:00Z
review text: In the papers [\textit{C. Greene}, \textit{A. Nijenhuis} and \textit{H. S. Wilf}, Adv. Math. 31, 104-109 (1979; Zbl 0398.05008) and J. Comb. Theory, Ser. A 37, 127-135 (1984; Zbl 0561.05004)] a remarkable probabilistic algorithm, the hook walk, was introduced. It was used there for two purposes: to give a new probabilistic proof of the hook formula and to generate random Young tableaux distributed according to the Plancherel measure. In the present paper we suggest new applications of the original Greene- Nijenhuis-Wilf algorithm and define a \(q\)-analog of this algorithm. Two applications of the generalized version of the algorithm are presented. The first application deals with an interesting family of probability distributions on the space of (infinite) Young tableaux. This family can be considered as a \(q\)-deformation of the Plancherel measure, and its distributions are in one-to-one correspondence with Markov traces on Hecke algebras (these traces arise in the algebraic construction of link and knot invariants defined by Jones). The new algorithm provides an efficient generation procedure for random Young tableaux with these distributions. The second application is related to a new interpretation of the well- known \(q\)-analog of the hook formula. We show that one can associate multiplicities (depending on \(q\) rationally) with the edges of a Young graph in such a way that the \(q\)-dimension of a Young diagram, defined recurrently, is given by the \(q\)-hook formula. In the particular case \(q=1\) all the edges are simple and the proof yields the classical formula.
Mathematics Subject Classification ID: 05E10
Mathematics Subject Classification ID: 05A30
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 571843
zbMATH Keywords: hook walk
zbMATH Keywords: hook formula
zbMATH Keywords: random Yound tableaux
zbMATH Keywords: Plancherel measure
zbMATH Keywords: Greene-Nijenhuis-Wilf algorithm
zbMATH Keywords: probability distributions
zbMATH Keywords: Markov traces
zbMATH Keywords: Hecke algebras
zbMATH Keywords: Young graph
zbMATH Keywords: Young diagram
author: S. V. Kerov
MaRDI profile type: Publication
cites work: A probabilistic proof of a formula for the number of Young tableaux of a given shape
cites work: Another probabilistic method in the theory of Young tableaux
cites work: The Hook Graphs of the Symmetric Group
cites work: Q3947818
cites work: On growing a random Young tableau
cites work: Locally semisimple algebras. Combinatorial theory and the \(K_ 0\)- functor
cites work: Hook formula and related identities
published in: Functional Analysis and Its Applications
description: scientific article; zbMATH DE number 571843