Content deleted Content added
→top: reformulated apparent meaning of analogy to tectonic plates to something that would seem more plausible |
short desc. |
||
| (24 intermediate revisions by 13 users not shown) | |||
Line 1:
{{Short description|The monoid 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 {{harvs|txt|first=Donald|last=Knuth|authorlink=Donald Knuth|year=1970}} (who called it the '''tableau algebra'''), using an operation given by {{harvs|txt|first=Craige|last=Schensted|authorlink=Craige Schensted|year=1961}} in his study of the [[longest increasing subsequence]] of a permutation.▼
▲In mathematics, the '''plactic monoid''' is the [[monoid]] of all words in the alphabet of positive integers modulo
It was named the "''monoïde plaxique''" by {{harvtxt|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.▼
▲It was named the "''monoïde plaxique''" by {{harvtxt|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 relation|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 of a monoid|presentation]]:
*The generators are the letters of the alphabet
*The relations are the '''elementary Knuth transformations''' ''yzx''
==Knuth equivalence==
Line 16 ⟶ 18:
*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). So the elements of the plactic monoid can be identified with the semistandard Young tableaux, which therefore also form a monoid.▼
[[Image:Young-Schensted.png|thumb|right|180px| Multiplying the element with tableau form (38)(1257) with the generator 4, illustrated using Young tableau notation:
<br/>• Using the plactic relations, (1257)*4 = 5*(1247)
<br/>• (38)*5 = 8*(35), so (5) replaces (8) in the second row
<br/>• (8) creates the third row
<br/>• 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 right with a generator is equivalent to [[Robinson-Schensted correspondence|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 [[Robinson-Schensted correspondence|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 ===
{{Main|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==
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.
==Growth==
Line 32 ⟶ 50:
==See also==
*[[Chinese monoid]]
*[[Robinson-Schensted correspondence]]
*[[Jeu de taquin]]
==References==
*{{Citation | last1=Duchamp | first1=Gérard | last2=Krob | first2=Daniel | title=Words, languages and combinatorics, II (Kyoto, 1992) | publisher=World Sci. Publ., River Edge, NJ | mr=1351284 | zbl=0875.68720 | year=1994 | chapter=Plactic-growth-like monoids | pages=124–142 |chapter-url=http://www.liafa.jussieu.fr/web9/rapportrech/description_en.php?idrapportrech=487}}
*{{Citation | last1=Fulton | first1=William | author1-link=William Fulton (mathematician) | title=Young tableaux | publisher=[[Cambridge University Press]] | series=London Mathematical Society Student Texts | isbn=978-0-521-56144-0 | mr=1464693 | zbl=0878.14034 | year=1997 | volume=35}}
*{{Citation | last1=Knuth | first1=Donald E. | author1-link=Donald Knuth | title=Permutations, matrices, and generalized Young tableaux | url=http://projecteuclid.org/euclid.pjm/1102971948 |mr=0272654 | year=1970 | journal=[[Pacific Journal of Mathematics]] | issn=0030-8730 | volume=34 | issue=3 | pages=709–727 | doi=10.2140/pjm.1970.34.709| doi-access=free }}
*{{Citation |last1=Lascoux |first1=Alain |first2=B. |last2=Leclerc |first3=J-Y. |last3=Thibon |chapter=The Plactic Monoid |chapter-url=http://www.combinatorics.net/lascoux/articles/plactic.ps |
*{{Citation | last1=Littelmann | first1=Peter | title=A plactic algebra for semisimple Lie algebras |
*{{Citation | author2-link=Marcel-Paul Schützenberger | last1=Lascoux | first1=Alain | last2=Schützenberger | first2=Marcel-P. | title=Noncommutative structures in algebra and geometric combinatorics (Naples, 1978) | publisher=CNR | ___location=Rome | series=Quaderni de La Ricerca Scientifica |mr=646486 | year=1981 | volume=109 | chapter=Le monoïde plaxique | pages=129–156|chapter-url=http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1981-1PlaxiqueNaples.pdf}}
* {{citation | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
*{{Citation | doi=10.4153/CJM-1961-015-3 | authorlink=Craige Schensted | last1=Schensted | first1=C. | title=Longest increasing and decreasing subsequences |mr=0121305 | year=1961 | journal=Canadian Journal of Mathematics | issn=0008-414X | volume=13 |
*{{Citation | last1=Schützenberger | first1=Marcel-Paul | title=Pour le monoïde plaxique | url=http://msh.revues.org/document2764.html |mr=1627563 | year=1997 | journal=Mathématiques, Informatique et Sciences Humaines | issn=0995-2314 | issue=140 | pages=5–10| doi=10.4000/msh.2764 | doi-access=free }}
==Further reading==
*{{citation | last=Green | first=James A. | authorlink=James Alexander Green | title=Polynomial representations of GL<sub>n</sub> | 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]] | isbn=978-3-540-46944-
[[Category:Combinatorics on words]]
| |||