“Plactic monoid”的意思、由来-开放百科全书

词条

Plactic monoid

释义

Definition
Knuth equivalence
Tableau ring
Growth
See also
References
Further reading

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.

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 the action of a generator of the plactic monoid resembles plates sliding past each other in an earthquake.

Definition

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.

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.

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.

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.

Growth

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

showing that there is polynomial growth of dimension .

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 |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 | pages=709–727 | doi=10.2140/pjm.1970.34.709}}
{{Citation |last1=Lascoux |first1=Alain |first2=B. |last2=Leclerc |first3=J-Y. |last3=Thibon |chapter=The Plactic Monoid |url=http://www.combinatorics.net/lascoux/articles/plactic.ps |deadurl=yes |archiveurl=https://web.archive.org/web/20110718165544/http://www.combinatorics.net/lascoux/articles/plactic.ps |archivedate=2011-07-18 |df= }}
{{Citation | last1=Littelmann | first1=Peter | title=A plactic algebra for semisimple Lie algebras | url=https://dx.doi.org/10.1006/aima.1996.0085 | doi=10.1006/aima.1996.0085 |mr=1424313 | year=1996 | journal=Advances in Mathematics | issn=0001-8708 | volume=124 | issue=2 | pages=312–331}}
{{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|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 | issue=0 | pages=179–191|url=https://books.google.com/books?id=G3sZ2zG8AiMC}}
{{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}}

Definition

Knuth equivalence

Tableau ring

Growth

See also

References

Further reading