Plactic monoid

The plactic monoid over some totally ordered alphabet (often the positive integers) is the monoid with the following presentation:

• The generators are the letters of the alphabet
• The relations are the elementary Knuth transformations yzx ≡ yxz whenever x < y ≤ z and xzy ≡ zxy whenever x ≤ y < z.

Two words are called Knuth equivalent if they represent the same element of the plactic monoid, or in other words if one can be obtained from the other by a sequence of elementary Knuth transformations.

Several properties are preserved by Knuth equivalence.

• If a word is a reverse lattice word, then so is any word Knuth equivalent to it.
• If two words are Knuth equivalent, then so are the words obtained by removing their rightmost maximal elements, as are the words obtained by removing their leftmost minimal elements.
• Knuth equivalence preserves the length of the longest nondecreasing subsequence, and more generally preserves the maximum of the sum of the lengths of k disjoint non-decreasing subsequences for any fixed k.

Multiplying the element with tableau form (38)(1257) with the generator 4 , illustrated using Young tableau notation:
• Using the plactic relations, (1257)*4 = 5*(1247)
• (38)*5 = 8*(35), so (5) replaces (8) in the second row
• (8) creates the third row
• The product then has the tableau form (8)(35)(1247)

Every word is Knuth equivalent to the word of a unique semistandard Young tableau (this means that each row is non-decreasing and each column is strictly increasing) over the same ordered alphabet, where the tableau may be read by rows or by columns. So the elements of the plactic monoid can be identified with the semistandard Young tableaux, which therefore also form a monoid.

Multiplying the word of a semistandard Young tableau to the left with a generator is equivalent to Schensted insertion into the Young tableau. In row order, the word of the tableau is equivalent to a product of increasingly longer nondecreasing sequences of generators. The new generator may be inserted in its proper place by either appending it if it is larger, and otherwise by repeatedly applying the plactic relations to move the out of sequence element to the next row. In the latter case, the out of order element replaces the leftmost entry larger than it in each row, and the displaced element is then inserted in the next row.

Since Schensted insertion preserves Young tableaux, this gives an inductive proof that elements of the plactic monoid can be written in a standard form corresponding to a Young tableau, and the construction defines a natural product of semistandard tableaux.

The tableau ring is the monoid ring of the plactic monoid, so it has a Z-basis consisting of elements of the plactic monoid, with the same product as in the plactic monoid.

There is a homomorphism from the plactic ring on an alphabet to the ring of polynomials (with variables indexed by the alphabet) taking any tableau to the product of the variables of its entries, corresponding to the abelianization of the plactic semigroup.

The generating function of the plactic monoid on an alphabet of size n is

${\displaystyle \Gamma (t)={\frac {1}{(1-t)^{n}}}{\frac {1}{(1-t^{2})^{n(n-1)/2}}}\ }$

showing that there is polynomial growth of dimension ${\displaystyle {\frac {n(n+1)}{2}}}$.

• Chinese monoid
• Robinson-Schensted correspondence
• Jeu de taquin

• Duchamp, Gérard; Krob, Daniel (1994), "Plactic-growth-like monoids", Words, languages and combinatorics, II (Kyoto, 1992), World Sci. Publ., River Edge, NJ, pp. 124–142, MR 1351284, Zbl 0875.68720
• Fulton, William (1997), Young tableaux, London Mathematical Society Student Texts, vol. 35, Cambridge University Press, ISBN 978-0-521-56144-0, MR 1464693, Zbl 0878.14034
• Knuth, Donald E. (1970), "Permutations, matrices, and generalized Young tableaux", Pacific Journal of Mathematics, 34 (3): 709–727, doi:10.2140/pjm.1970.34.709, ISSN 0030-8730, MR 0272654
• Lascoux, Alain; Leclerc, B.; Thibon, J-Y., "The Plactic Monoid", archived from the original on 2011-07-18 {{citation}}: Missing or empty |title= (help)
• Littelmann, Peter (1996), "A plactic algebra for semisimple Lie algebras", Advances in Mathematics, 124 (2): 312–331, doi:10.1006/aima.1996.0085, ISSN 0001-8708, MR 1424313
• Lascoux, Alain; Schützenberger, Marcel-P. (1981), "Le monoïde plaxique" (PDF), Noncommutative structures in algebra and geometric combinatorics (Naples, 1978), Quaderni de La Ricerca Scientifica, vol. 109, Rome: CNR, pp. 129–156, MR 0646486
• Lothaire, M. (2011), Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, vol. 90, With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.), Cambridge University Press, ISBN 978-0-521-18071-9, Zbl 1221.68183
• Schensted, C. (1961), "Longest increasing and decreasing subsequences", Canadian Journal of Mathematics, 13: 179–191, doi:10.4153/CJM-1961-015-3, ISSN 0008-414X, MR 0121305, S2CID 247197258
• Schützenberger, Marcel-Paul (1997), "Pour le monoïde plaxique", Mathématiques, Informatique et Sciences Humaines (140): 5–10, doi:10.4000/msh.2764, ISSN 0995-2314, MR 1627563

• Green, James A. (2007), Polynomial representations of GL_n, Lecture Notes in Mathematics, vol. 830, With an appendix on Schensted correspondence and Littelmann paths by K. Erdmann, J. A. Green and M. Schocker (2nd corrected and augmented ed.), Berlin: Springer-Verlag, ISBN 978-3-540-46944-5, Zbl 1108.20044