کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6419732 | 1631647 | 2011 | 33 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm](/preview/png/6419732.png)
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.
Journal: Advances in Applied Mathematics - Volume 46, Issues 1â4, January 2011, Pages 610-642