### 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 language | English (US) |
---|---|

Pages (from-to) | 610-642 |

Number of pages | 33 |

Journal | Advances in Applied Mathematics |

Volume | 46 |

Issue number | 1-4 |

DOIs | |

State | Published - Jan 1 2011 |

### Fingerprint

### Keywords

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

### ASJC Scopus subject areas

- Applied Mathematics