In mathematics, the plactic monoid is the
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
of all words in the alphabet of positive integers modulo
Knuth equivalence 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 (who called it the tableau algebr ...
. Its elements can be identified with semistandard
Young tableaux In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and ...
. It was discovered by (who called it the tableau algebra), using an operation given by in his study of the
longest increasing subsequence In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subseq ...
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 to
plate tectonics
Plate tectonics (from the la, label=Late Latin, tectonicus, from the grc, τεκτονικός, lit=pertaining to building) is the generally accepted scientific theory that considers the Earth's lithosphere to comprise a number of large ...
("tectonique des plaques" in French), as elementary relations that generate the
equivalence allow conditional commutation of generator symbols: they can sometimes slide across each other (in apparent analogy to tectonic plates), but not freely.
Definition
The plactic monoid over some totally ordered alphabet (often the positive integers) is the monoid with the following
presentation
A presentation conveys information from a speaker to an audience. Presentations are typically demonstrations, introduction, lecture, or speech meant to inform, persuade, inspire, motivate, build goodwill, or present a new idea/product. Presenta ...
:
*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''.
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 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''.
Correspondence with Semistandard Young Tableaux
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.
Jeu de Taquin
Two skew Young Tableaux are
Jeu de taquin In the mathematical field of combinatorics, jeu de taquin is a construction due to which defines an equivalence relation on the set of skew standard Young tableaux. A jeu de taquin slide is a transformation where the numbers in a tableau are move ...
equivalent if and only if their word readings are Knuth equivalent, i.e. correspond to equivalent elements of the plactic group. This gives an alternative definition of the plactic group product directly in terms of Young tableaux. Two tableaux may be multiplied by drawing them both around an empty rectangle to form a skew tableau, and using Jeu de taquin slides to rectify it.
Tableau ring
The tableau ring is the
monoid ring
In abstract algebra, a monoid ring is a ring constructed from a ring and a monoid, just as a group ring is constructed from a ring and a group.
Definition
Let ''R'' be a ring and let ''G'' be a monoid. The monoid ring or monoid algebra of ''G'' o ...
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
In mathematics, more specifically in abstract algebra, the commutator subgroup or derived subgroup of a group is the subgroup generated by all the commutators of the group.
The commutator subgroup is important because it is the smallest normal s ...
of the plactic semigroup.
Growth
The
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
of the plactic monoid on an alphabet of size ''n'' is
:
showing that there is polynomial growth of dimension
.
See also
*
Chinese monoid In mathematics, the Chinese monoid is a monoid generated by a totally ordered alphabet with the relations ''cba'' = ''cab'' = ''bca'' for every ''a'' ≤ ''b'' ≤ ''c''. An algorithm similar to Schensted's algorithm yields characterisation of the ...
*
Robinson-Schensted correspondence
*
Jeu de taquin In the mathematical field of combinatorics, jeu de taquin is a construction due to which defines an equivalence relation on the set of skew standard Young tableaux. A jeu de taquin slide is a transformation where the numbers in a tableau are move ...
References
*
*
*
*
*
*
*
*
*
Further reading
*{{citation , last=Green , first=James A. , authorlink=James Alexander Green , title=Polynomial representations of GL
n , others=With an appendix on Schensted correspondence and Littelmann paths by K. Erdmann, J. A. Green and M. Schocker , edition=2nd corrected and augmented , zbl=1108.20044 , series=Lecture Notes in Mathematics , volume=830 , location=Berlin , publisher=
Springer-Verlag
Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.
Originally founded in 1842 in ...
, isbn=978-3-540-46944-5 , year=2007
Combinatorics on words
Semigroup theory