Monoïde plaxique
# 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.

## Définition

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

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.
* 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

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.

