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

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

2008-01-08

arxiv.org/abs/0801.1319v2

Advances in Applied Math., Vol 46 (2011), no.1-4, 610-642

Mathematics

Combinatorics

28 pages; companion software available at the authors' websites; v2 contains an Appendix by O. Zeitouni and the second author,

Scientific paper

We define and study the Plancherel-Hecke probability measure on Young diagrams; the Hecke algorithm of [Buch-Kresch-Shimozono-Tamvakis-Yong '06] is interpreted as a polynomial-time exact sampling algorithm for this measure. Using the results of [Thomas-Yong '07] 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 '61] and of [Knuth '70], 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 '77], [Logan-Shepp '77] and others on the ``longest increasing subsequence problem'' for permutations. We also include a related extension of [Aldous-Diaconis '99] 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.

Affiliated with

Also associated with

No associations

Rating

Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-669058