It was named the "monoïde plaxique" by Lascoux & Schützenberger (1981), who allowed any totally ordered alphabet in the definition. The etymology of the word "plaxique" is unclear; it may refer to plate tectonics ("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.
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 transformationsyzx ≡ yxz whenever x < y ≤ z and xzy ≡ zxy whenever x ≤ y < z.
Knuth equivalenceedit
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 tableauxedit
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.
Two skew Young Tableaux are Jeu de taquin 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 ringedit
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.
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
Lascoux, Alain; Leclerc, B.; Thibon, J-Y., , 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, ISBN978-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
Further readingedit
Green, James A. (2007), Polynomial representations of GLn, 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, ISBN978-3-540-46944-5, Zbl 1108.20044
April 07, 2024
plactic, monoid, mathematics, plactic, monoid, monoid, words, alphabet, positive, integers, modulo, knuth, equivalence, elements, identified, with, semistandard, young, tableaux, discovered, donald, knuth, 1970, called, tableau, algebra, using, operation, give. 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 Donald Knuth 1970 who called it the tableau algebra using an operation given by Craige Schensted 1961 in his study of the longest increasing subsequence of a permutation It was named the monoide plaxique by Lascoux amp Schutzenberger 1981 who allowed any totally ordered alphabet in the definition The etymology of the word plaxique is unclear it may refer to plate tectonics 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 Contents 1 Definition 2 Knuth equivalence 3 Correspondence with semistandard Young tableaux 3 1 Jeu de Taquin 4 Tableau ring 5 Growth 6 See also 7 References 8 Further readingDefinition editThe 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 lt y z and xzy zxy whenever x y lt z Knuth equivalence editTwo 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 edit nbsp 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 Jeu de Taquin edit Main article Jeu de taquin Two skew Young Tableaux are Jeu de taquin 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 editThe 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 Growth editThe generating function of the plactic monoid on an alphabet of size n is G t 1 1 t n1 1 t2 n n 1 2 displaystyle Gamma t frac 1 1 t n frac 1 1 t 2 n n 1 2 nbsp showing that there is polynomial growth of dimension n n 1 2 displaystyle frac n n 1 2 nbsp See also editChinese monoid Robinson Schensted correspondence Jeu de taquinReferences editDuchamp Gerard 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 a href Template Citation html title Template Citation citation a 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 Schutzenberger Marcel P 1981 Le monoide 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 Schutzenberger Marcel Paul 1997 Pour le monoide plaxique Mathematiques Informatique et Sciences Humaines 140 5 10 doi 10 4000 msh 2764 ISSN 0995 2314 MR 1627563Further reading editGreen James A 2007 Polynomial representations of GLn 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 Retrieved from https en wikipedia org w index php title Plactic monoid amp oldid 1163780862, wikipedia, wiki, book, books, library,
