Korean J. Math. Vol. 21 No. 3 (2013) pp.223-236
DOI: https://doi.org/10.11568/kjm.2013.21.3.223

Some properties of Schensted algorithm using Viennot's geometric interpretation

Article Sidebar

PDF
Published: Aug 8, 2013
Mathematics Subject Classification:
05E10

Main Article Content

Jaejin Lee

Abstract

Schensted algorithm was first described in 1938 by Robinson, in a paper dealing with an attempt to prove the correctness of the Littlewood-Richardson rule. Schensted rediscovered Schensted algorithm independently in 1961 and Viennot \cite{viennot} gave a geometric interpretation for Schensted algorithm in 1977. In this paper we describe some properties of Schensted algorithm using Viennot's geometric interpretation.



Article Details

References

[1] A. Berele, A Schensted-type correspondence for the symplectic group, J. Combin. Theory Ser. A 43 (1986), 320–328. Google Scholar

[2] C. Greene, An extension of Schensted’s theorem, Adv. in Math., 14 (1974), 254–265. Google Scholar

[3] J. J. Lee, A Schensted algorithm for shifted rim hook tableaux, Korean J. Math., 31 (1994), 179–203. Google Scholar

[4] D. E. Knuth, Permutations, matrices and generalized Young tableaux, Pacific J. Math., 34 (1970), 709–727. Google Scholar

[5] G. de B. Robinson, On the representations of the symmetric group , Amer. J. Math., 60, (1938), 745–760. Google Scholar

[6] B. E. Sagan, Shifted tableaux, Schur Q-functions and a conjecture of R. Stanley, J. Combin. Theory Ser. A 45 (1987), 62–103. Google Scholar

[7] B. E. Sagan, The symmetric group, Springer-Verlag, New York, 2000. Google Scholar

[8] B. E. Sagan and R. P. Stanley, Robinson-Schensted algorithms for skew tableaux, Google Scholar

[9] J. Combin. Theory Ser. A, 55 (1990), 161–193. Google Scholar

[10] C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math., 13 (1961), 179–191. Google Scholar

[11] D. W. Stanton and D. E. White, A Schensted algorithm for rim hook tableaux, J. Combin. Theory Ser. A 40 (1985), 211–247. Google Scholar

[12] M. P. Schu ̈tzenberger, Quelques remarques sur une construction de Schensted, Math., Scand. 12 (1963), 117–128. Google Scholar

[13] G. Viennot, Une forme g eom etrique de la correspondance de Robinson-Schensted, in Combiatoire et Repr esentation du Groupe Sym etrique, D. Foata ed., Lecture Notes in Math., Vol. 579, Springer-Verlag, New York, NY, 1977, 29-58. Google Scholar