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

Hugh Thomas, Alexander Yong

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)610-642
Number of pages33
JournalAdvances in Applied Mathematics
Volume46
Issue number1-4
DOIs
StatePublished - Jan 1 2011

Keywords

  • Hecke insertion
  • Increasing tableaux
  • Jeu de taquin
  • Longest increasing subsequences

ASJC Scopus subject areas

  • Applied Mathematics

Fingerprint Dive into the research topics of 'Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm'. Together they form a unique fingerprint.

  • Cite this