Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm

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.