Monoïde plaxique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 | modifier le code]

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\le z;
    • xzy\equiv zxy lorsque x\le y<z.

Équivalence de Knuth[modifier | modifier le code]

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 muni d'une structure de monoïde.

L'algèbre des tableaux[modifier | modifier le code]

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 | modifier le code]

Notes[modifier | modifier le code]

  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.

Bibliographie[modifier | modifier le code]

  • 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