Fiche du document
2011
- handle: 10670/1.5r7cgp
- Thomas, Hugh et Yong, Alexander (2011). « Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm ». Advances in Applied Mathematics, 46(1-4), pp. 610-642.
Ce document est lié à :
http://archipel.uqam.ca/8515/
Ce document est lié à :
http://dx.doi.org/10.1016/j.aam
Ce document est lié à :
doi:10.1016/j.aam.2009.07.005
Sujets proches
Poses plastiques Model artists Tableaux vivants Living models Living statues Living picturesCiter ce document
Hugh Thomas et al., « Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm », UQAM Archipel : articles scientifiques, ID : 10670/1.5r7cgp
Métriques
Partage / Export
Résumé
We define and study the Plancherel–Hecke probability measure on Young diagrams; the Hecke algorithm of Buch–Kresch–Shimozono–Tamvakis–Yong is interpreted as a polynomial-time exact sampling algorithm for this measure. Using the results of Thomas–Yong on jeu de taquin for increasing tableaux, a symmetry property of the Hecke algorithm is proved, in terms of longest strictly increasing/decreasing subsequences of words. This parallels classical theorems of Schensted and of Knuth, respectively, on the Schensted and Robinson–Schensted–Knuth algorithms. We investigate, and conjecture about, the limit typical shape of the measure, in analogy with work of Vershik–Kerov, Logan–Shepp and others on the “longest increasing subsequence problem” for permutations. We also include a related extension of Aldous–Diaconis on patience sorting. Together, these results provide a new rationale for the study of increasing tableau combinatorics, distinct from the original algebraic-geometric ones concerning K-theoretic Schubert calculus.