TY - JOUR
T1 - Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm
AU - Thomas, Hugh
AU - Yong, Alexander
N1 - Funding Information:
H.T. was supported by an NSERC Discovery Grant. A.Y. was supported by NSF grants DMS 0601010 and DMS 0901331, and a U. Minnesota DTC grant during the Spring 2007; he also utilized the resources of the Fields Institute, and of Algorithmics Incorporated, in Toronto, while a visitor. We would like to thank Ofer Zeitouni for allowing us to include his proof for the α > αcritical = 21 case of Theorem 1.9 and for his extensive help during this project. We also thank Alexander Barvinok, Nantel Bergeron, Alexei Borodin, Sergey Fomin, Christian Houdré, Nicolas Lanchier, Igor Pak, Eric Rains, Mark Shimozono, Richard Stanley, Dennis Stanton, Craig Tracy and Alexander Woo for helpful correspondence. We also thank the anonymous referee for detailed comments and corrections.
PY - 2011/1
Y1 - 2011/1
N2 - 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.
AB - 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.
KW - Hecke insertion
KW - Increasing tableaux
KW - Jeu de taquin
KW - Longest increasing subsequences
UR - http://www.scopus.com/inward/record.url?scp=79953718347&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79953718347&partnerID=8YFLogxK
U2 - 10.1016/j.aam.2009.07.005
DO - 10.1016/j.aam.2009.07.005
M3 - Article
AN - SCOPUS:79953718347
SN - 0196-8858
VL - 46
SP - 610
EP - 642
JO - Advances in Applied Mathematics
JF - Advances in Applied Mathematics
IS - 1-4
ER -