Monoïde plaxique

En mathématiques, et notamment en combinatoire, le monoïde plaxique est le monoïde quotient du monoïde libre sur un alphabet totalement ordonné par l'équivalence de Knuth. Il a été décrit pour la première fois, sous le nom de tableau algebra, par Knuth (1970), sur l'alphabet des entiers positifs au moyen d'une opération donnée par Schensted (1961) dans son étude de la plus longue sous-séquence croissante d'une permutation. Les éléments du monoïde plaxique peuvent être identifiés aux tableaux de Young.

Le nom « monoïde plaxique » apparaît dans Lascoux et Schützenberger (1981), qui l'étendent aux alphabets quelconques totalement ordonnés. Le mot « plaxique » est une réminiscence de la tectonique des plaques^[1].

Définition modifier

Le monoïde plaxique sur un alphabet totalement ordonné (souvent les entiers positifs) est le monoïde avec la présentation suivante :

Les générateurs sont les lettres de l’alphabet.
Les relations sont les transformations de Knuth élémentaires. Si $x,y,z$ sont des lettres, alors on a :
- $yzx\equiv yxz$ lorsque $x<y\leq z$ ;
- $xzy\equiv zxy$ lorsque $x\leq y<z$ .

Équivalence de Knuth modifier

Deux mots sont dits équivalent au sens de Knuth s'ils représentent le même élément du monoïde plaxique ou, en d'autres termes, si l'on peut obtenir l'un à partir de l’autre par une séquence de transformations de Knuth élémentaires. La relation d'équivalence est aussi appelée congruence plaxique.

Plusieurs propriétés sont préservées par l’équivalence de Knuth.

tout mot équivalent à un mot de Yamanouchi est aussi un mot de Yamanouchi^[2].
si deux mots sont équivalents au sens de Knuth, les mots obtenus en supprimant leur élément maximal le plus à droite sont équivalents, de même qui les mots obtenus en supprimant le élément minimal le plus à gauche.
L'équivalence de Knuth préserve la longueur de la plus longue sous-séquence non décroissante, et plus généralement préserve le maximum de la somme des longueurs de $k$ sous-séquences non décroissantes disjointes, pour tout $k$ .

Tout mot est équivalent au sens de Knuth à un unique tableau de Young. Par cette identification, les tableaux de Young semi-standard sont munis d'une structure de monoïde.

L'algèbre des tableaux modifier

L'algèbre des tableaux est l'algèbre de monoïde du monoïde plaxique, sur l’anneau des entiers. Elle a une base formée des éléments du monoïde plaxique, avec le produit du monoïde plaxique.

Il existe un morphisme de l'algèbre des tableaux dans l'anneau des polynômes dont les variables sont les lettres de l'alphabet qui, à chaque tableau, associe le monôme formé du produit des variables de ses entrées.

Voir aussi modifier

Monoïde chinois

Notes modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « plactic monoid » (voir la liste des auteurs).

↑ (Lascoux, Leclerc Thibon, 2002), Notes
↑ Un mot de Yamanouchi est un mot tel que, dans tout suffixe, toute lettre $x$ apparaît au moins aussi fréquemment qu'une lettre $y>x$ . Cette définition est répandue lorsque l'alphabet est l'ensemble des entiers naturels.

Bibliographie modifier

William Fulton, Young tableaux, Cambridge University Press, coll. « London Mathematical Society Student Texts » (n^o 35), 1997, 260 p. (ISBN 978-0-521-56724-4, lire en ligne) lien Math Reviews

Donald E. Knuth, « Permutations, matrices, and generalized Young tableaux », Pacific Journal of Mathematics, vol. 34,‎ 1970, p. 709–727 (lire en ligne) lien Math Reviews

Alain Lascoux, Bernard Leclerc et Jean-Yves Thibon, « The plactic monoid », dans M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2002 (ISBN 978-0-521-81220-7), p. 164-196

Alain Lascoux et Marcel-Paul Schützenberger, « Le monoîde plaxique », dans Noncommutative structures in algebra and geometric combinatorics (Naples, 1978), Rome, CNR, coll. « Quaderni de La Ricerca Scientifica » (n^o 109), 1981 (lire en ligne), p. 129–156 lien Math Reviews

Craige Schensted, « Longest increasing and decreasing subsequences », Canadian Journal of Mathematics, vol. 13,‎ 1961, p. 179–191 (lire en ligne) lien Math Reviews

Marcel-Paul Schützenberger, « Pour le monoïde plaxique », Mathématiques Informatique et Sciences Humaines, vol. 140,‎ 1997, p. 5–10 (ISSN 0995-2314, lire en ligne) lien Math Reviews

Antoine Abram et Christophe Reutenauer, « The stylic monoid », Semigroup Forum, vol. 105, n^o 1,‎ 2022, p. 1–45 (DOI 10.1007/s00233-022-10285-3, arXiv 2106.06556).
Christian Choffrut, « Grammic monoids with three generators », Semigroup Forum, vol. 105, n^o 3,‎ 1^er décembre 2022, p. 680–692 (DOI 10.1007/s00233-022-10316-z, arXiv 2207.13043).
Thomas Aird et Duarte Ribeiro, « Tropical representations and identities of the stylic monoid », Semigroup Forum, vol. 106, n^o 1,‎ février 2023, p. 1–23 (DOI 10.1007/s00233-022-10328-9 , lire en ligne).

Portail des mathématiques

[1] (Lascoux, Leclerc Thibon, 2002), Notes

[2] Un mot de Yamanouchi est un mot tel que, dans tout suffixe, toute lettre $x$ apparaît au moins aussi fréquemment qu'une lettre $y>x$ . Cette définition est répandue lorsque l'alphabet est l'ensemble des entiers naturels.

[1]

[2]