Jeu de taquin de Schützenberger

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

En mathématiques, et notamment en combinatoire, le jeu de taquin est une construction de Marcel-Paul Schützenberger introduite dans Schützenberger (1977) qui définit une relation d'équivalence sur l'ensemble des tableaux de Young. Un glissement est une transformation où les nombres d'un tableau sont déplacés de façon similaire à celle d'un jeu de taquin traditionnel. Deux tableaux sont équivalents pour le jeu de taquin s'ils peuvent être transformés l'un dans l'autre par une suite de glissements.

Glissement dans un jeu de taquin[modifier | modifier le code]

Les opérations de glissement: ici x<y<z.
Exemple d'un glissement : 2 glisse dans la cellule vide, 4 monte dans la l'ancienne cellule de 2, et 6 glisse vers la gauche.

Étant donné un tableau de Young gauche T de forme gauche \lambda\setminus\mu, on choisit une cellule vide c adjacente au tableau qui peut être ajoutée au tableau. Cela signifie que c a un côté en commun avec une cellule de T, et que \{c\} \cup \lambda\setminus\mu est encore une forme gauche. Il y a deux types de glissements, selon que c est dans la partie supérieure gauche, ou dans la partie inférieure droite de T.

Supposons pour commencer que c est dans la partie supérieure gauche. On fait glisser le nombre de la cellule voisine de c dans c ; si c a deux cellules voisines, on prend le plus petit des nombres, et si les nombres sont égaux, la cellule du bas : cette règle assure que la propriété du tableau d'avoir des lignes non décroissantes et des colonnes croissantes est préservée. Si la cellule que l'on vient de vider n'a pas de voisin à droite ou en dessous, le glissement est terminé. Sinon, on fait glisser le nombre de la cellule voisine avec la même règle que précédemment, et on continue jusqu'au bout. À la fin, le tableau obtenu est toujours un tableau de Young (pas nécessairement gauche).

L'autre type de glissement, lorsque c est dans la partie inférieure droite de T, opère de la même manière, mais dans la direction opposée. Dans ce cas, on glisse un nombre dans une cellule vide depuis le voisin de gauche ou de dessus, en prenant le nombre le plus grand des nombres s'il y a un choix. Les deux types de glissements sont l'inverse l'un de l'autre : un glissement d'un des deux types peut être inversé par un glissement le l'autre type.

L'involution de Schützenberger[modifier | modifier le code]

Le jeu de taquin permet de définir une opération sur les tableaux de Young d'une forme donnée ; cette opération est en fait une involution, même si ce n'est pas évident à partir de la définition. L'opération est la suivante : on commence par vider la cellule supérieure gauche, ce qui transforme le tableau en un tableau gauche. On applique alors un glissement de taquins pour transformer le tableau gauche en un tableau droit. Ceci libère une cellule sur le bord du tableau. Cette cellule est remplie avec l'opposé du nombre qui a été enlevé dans le coin supérieur gauche. Cette valeur négative est considérée comme faisant partie d'un nouveau tableau, et sa position ne changera plus dans la suite. Tant qu'il reste encore des entrées dans le tableau d'origine, on répète l'opération de suppression d'une valeur x dans le coin supérieur gauche, de glissement de taquins, et d'insertion de la valeur -x dans la cellule libérée. À la fin de ce processus, les valeurs négatives sont réordonnées pour que les lignes et colonnes soient croissantes. Enfin, une constante appropriée est ajoutée à toutes les entrées pour obtenir un tableau de Young à entrées positives.

Applications[modifier | modifier le code]

Tout tableau de Young gauche peut être transformé en un tableau de Young unique par une suite de glissements, donc tout tableau de Young gauche est équivalent à un tableau de Young. L'équivalence définie par les glissements est en fait la même que l'équivalence de Knuth qui définit le monoïde plaxique.

Le jeu de taquin est étroitement lié à la correspondance de Robinson-Schensted-Knuth, et à la règle de Littlewood-Richardson.

Références[modifier | modifier le code]