Robinson-Schensted-Knuth algorithm, jeu de taquin, and Kerov-Vershik measures on infinite tableaux

DOI10.1137/130930169MaRDI QIDQ3192152zbMATHOpenAlexFDO

Authors Piotr Śniady

Publication date 26 September 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dynamical systemYoung tableaujeu de taquinRobinson-Schensted-Knuth algorithmasymptotic representation theory of symmetric groupsisomorphism of measure-preserving systemsThoma characters of the infinite symmetric groupVershik-Kerov measures

Mathematics Subject Classification ID

Combinatorial probability (60C05) Combinatorial aspects of representation theory (05E10) Dynamical aspects of measure-preserving transformations (37A05) Representations of finite symmetric groups (20C30) Representations of infinite symmetric groups (20C32)

Abstract: We investigate Robinson-Schensted-Knuth algorithm (RSK) and Sch"utzenberger's jeu de taquin in the infinite setup. We show that the recording tableau in RSK defines an isomorphism of the following two dynamical systems: (i) a sequence of i.i.d. random letters equipped with Bernoulli shift, and (ii) a random infinite Young tableau (with the distribution given by Vershik-Kerov measure, corresponding to some Thoma character of the infinite symmetric group) equipped with jeu de taquin transformation. As a special case we recover the results on non-colliding random walks and multidimensional Pitman transform.

Recommendations

• Jeu de taquin dynamics on infinite Young tableaux and second class particles
• The Characters of the Infinite Symmetric Group and Probability Properties of the Robinson–Schensted–Knuth Algorithm
• Conditioned random walks and the RSK correspondence
• scientific article; zbMATH DE number 3966079
• Poisson limit of bumping routes in the Robinson-Schensted correspondence

Cited in

(25)

• Zigzag diagrams and Martin boundary
• Jeu de taquin dynamics on infinite Young tableaux and second class particles
• Iterating the RSK bijection
• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
• The Characters of the Infinite Symmetric Group and Probability Properties of the Robinson–Schensted–Knuth Algorithm
• Three theorems on the uniqueness of the Plancherel measure from different viewpoints
• Central measures on multiplicative graphs, representations of Lie algebras and weight polytopes
• Harmonic functions on multiplicative graphs and inverse Pitman transform on infinite random paths
• scientific article; zbMATH DE number 3966079 (Why is no real title available?)
• The problem of combinatorial encoding of a continuous dynamics and the notion of transfer of paths in graphs
• Combinatorial encoding of Bernoulli schemes and the asymptotic behavior of Young tableaux
• Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
• Law of large numbers for infinite random matrices over a finite field
• Periodic Pólya urns, the density method and asymptotics of Young tableaux
• Second class particles and limit shapes of evacuation and sliding paths for random tableaux.
• Backward jeu de taquin slides for composition tableaux and a noncommutative Pieri rule
• The Schur-Weyl graph and Thoma's theorem
• Ergodicity and totality of partitions associated with the RSK correspondence
• Poisson limit of bumping routes in the Robinson-Schensted correspondence
• Asymptotics of the partition of the cube into Weyl simplices and an encoding of a Bernoulli scheme
• \(K\)-Knuth equivalence for increasing tableaux
• A remark on the isomorphism between the Bernoulli scheme and the Plancherel measure
• Hydrodynamic limit of the Robinson–Schensted–Knuth algorithm
• An analogue of the Robinson-Schensted-Knuth correspondence and non-symmetric Cauchy kernels for truncated staircases
• Estimate of time needed for a coordinate of a Bernoulli scheme to fall into the first column of a Young tableau

This page was built for publication: Robinson-Schensted-Knuth algorithm, jeu de taquin, and Kerov-Vershik measures on infinite tableaux

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