plactic monoid
≈ 2 min read
Names in other languages
- УкраїнськаПлактичний моноїд
- Françaismonoïde plaxique
- Englishplactic monoid
- eoplaka monoido
- 日本語プラクティックモノイド
- 한국어플랙틱 모노이드
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 algebra), 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 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.
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 algebra), 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 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.
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 \Gamma(t) = \frac{1}{(1-t)^n} \frac{1}{(1-t^2)^{n(n-1)/2}} \ showing that there is polynomial growth of dimension \frac{n(n+1)}{2} .
See also
Chinese monoid Robinson-Schensted correspondence Jeu de taquin
References
Further reading
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378036129 under CC BY-SA 4.0; modifications have been made.