On subsequences and certain elements which determine various cells in S_n

C. A. Pallikaros, Thomas McDonough

Research output: Contribution to journalArticlepeer-review

4 Citations (SciVal)


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.
Original languageEnglish
Pages (from-to)1249-1263
Number of pages15
JournalJournal of Algebra
Issue number3
Publication statusPublished - 01 Feb 2008


  • Symmetric groups
  • Young tableaux
  • Kazhdan–Lusztig cells
  • Coxeter groups


Dive into the research topics of 'On subsequences and certain elements which determine various cells in S_n'. Together they form a unique fingerprint.

Cite this