In mathematics, the plactic monoid is the monoid of all words in the alphabet of positive integers modulo Knuth equivalence. Its elements can be identified with semistandard Young tableaux. It was discovered by , using an operation given by in his study of the longest increasing subsequence of a permutation. It was named the "monoïde plaxique" by , who allowed any totally ordered alphabet in the definition. The etymology of the word "plaxique" is unclear; it may refer toplate tectonics, as elementary relations that generate the equivalence allow conditional commutation of generator symbols: they can sometimes slide across each other, but not freely.
Definition
The plactic monoid over some totally ordered alphabet is the monoid with the following presentation:
The relations are the elementary Knuth transformationsyzx = yxz whenever x < y ≤ z and xzy = zxy whenever x ≤ y < z.
Knuth equivalence
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 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.
Every word is Knuth equivalent to the word of a unique semistandard Young tableau. So the elements of the plactic monoid can be identified with the semistandard Young tableaux, which therefore also form a monoid.
Tableau ring
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 taking any tableau to the product of the variables of its entries.
Growth
The generating function of the plactic monoid on an alphabet of size n is showing that there is polynomial growth of dimension.
