On subsequences and certain elements which determine various cells in Sn
Date
2008Source
Journal of AlgebraVolume
319Issue
3Pages
1249-1263Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
We study the relation between certain increasing and decreasing subsequences occurring in the row form of certain elements in the symmetric group, following Schensted [C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961) 179-191] and Greene [C. Greene, An extension of Schensted's theorem, Adv. Math. 14 (1974) 254-265], and the Kazhdan-Lusztig cells [D.A. Kazhdan, G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979) 165-184] of the symmetric group to which they belong. We show that, in the two-sided cell corresponding to a partition λ, there is an explicitly defined element dλ, each of whose prefixes can be used to obtain a left cell by multiplying the cell containing the longest element of the parabolic subgroup associated with λ on the right. Furthermore, we show that the elements of these left cells are those which possess increasing and decreasing subsequences of certain types. The results in this paper lead to efficient algorithms for the explicit descriptions of many left cells inside a given two-sided cell, and the authors have implemented these algorithms in GAP. © 2007 Elsevier Inc. All rights reserved.