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

Thomas, Hugh et Yong, Alexander (2011). « Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm ». Advances in Applied Mathematics, 46(1-4), pp. 610-642.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (387kB)

Résumé

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.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	Longest increasing subsequences; Hecke insertion; Jeu de taquin; Increasing tableaux
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Hugh R. Thomas
Date de dépôt:	24 mai 2016 15:14
Dernière modification:	31 mai 2016 13:06
Adresse URL :	http://archipel.uqam.ca/id/eprint/8515

Modifier les métadonnées (propriétaire du document)

Statistiques