Tableau de Young

En mathématiques, les tableaux de Young sont des objets combinatoires qui jouent un rôle important en théorie des représentations des groupes et dans la théorie des fonctions symétriques. Ils permettent en particulier de construire les représentations irréductibles du groupe symétrique, ainsi que celles du groupe général linéaire sur le corps des complexes.

Les tableaux de Young ont été introduits par Alfred Young, un mathématicien de l'université de Cambridge, en 1900. Ils ont été appliqués à l'étude du groupe symétrique par Georg Frobenius en 1903. Leur théorie a été développée par de nombreux mathématiciens, parmi lesquels Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger et Richard P. Stanley.

Ces tableaux peuvent apparaître également lors de la réduction de Jordan d'endomorphismes nilpotents.

Définition

Diagramme de Young

Diagramme de Young de forme (5, 4, 1), notation anglaise où la première ligne de 5 cases est en haut, puis la deuxième de 4 cases, et la dernière, de 1 case, est en bas.

Diagramme de Young de forme (5, 4, 1), notation française où la première ligne de 5 cases est en bas, puis la deuxième de 4 cases, et la dernière, de 1 cases, est en haut.

Un diagramme de Young (aussi appelé diagramme de Ferrers) est une collection finie de cases, ou cellules, organisée en lignes alignées à gauche, avec la propriété que les longueurs des lignes décroissent au sens large (chaque ligne est aussi longue ou plus longue que la précédente). La suite des longueurs des lignes donne une partition $\lambda$ de l'entier $n$ qui est le nombre total de cases du diagramme. L'image à droite montre le diagramme associé à la partition $(5,4,1)$. La partition $\lambda$ est appelée la forme du diagramme. L'inclusion d'un diagramme de Young dans un autre définit une structure de treillis connue sous le nom de treillis de Young. Si l'on énumère le nombre de cases d'un diagramme par colonnes, on obtient une autre partition, appelée la partition conjuguée ou transposée de $\lambda$.

Les cases d'un diagramme de Young sont généralement indicées par des paires d'entiers, le premier indice dénotant la ligne, le deuxième la colonne. Toutefois, il existe deux conventions pour représenter ces diagrammes, la première qui place chaque ligne en dessous de la précédente, la deuxième qui la place au-dessus. La première convention est principalement utilisée par les anglophones, la deuxième est souvent préférée par les francophones ; c'est pourquoi ces notations sont appelées notation anglaise et notation française. La notation anglaise correspond aux matrices, la notation française aux coordonnées cartésiennes.

Tableau de Young

Le diagramme de Young associé à la partition 7=3+3+1 (notation française).

Un tableau de Young semi-standard de forme $(3,3,1)$ à valeurs dans $[4]$. Son poids est $(1,3,1,2)$.

Pour un entier naturel $m$, on note $[m]$ l'ensemble des entiers de $1$ à $m$. Un tableau de Young est obtenu en remplissant les cellules d'un diagramme de Young avec des entiers. À l'origine^[Quoi ?], les entrées étaient des variables $x_{1},x_{2},x_{3},\ldots$; maintenant, on utilise des entiers. Dans leur application originale aux représentations du groupe symétrique, les tableaux de Young ont $n$ entrées distinctes, associées arbitrairement aux cellules du tableau. Un tableau de Young est standard quand les valeurs des entrées sont distinctes deux-à-deux, et sont les entiers de 1 jusqu'au nombre total de cellules, et tel que les entrées sont strictement croissantes dans les lignes et dans les colonnes. Un tableau est semi-standard quand les lignes sont croissantes au sens large, et les colonnes croissantes au sens strict, et quand tous les entiers de 1 à la valeur maximale sont présentes.

Le poids d'un tableau est une suite qui, pour chaque valeur présente dans un tableau de Young, indique le nombre de fois qu'elle y figure. Ainsi, un tableau de Young semi-standard est un tableau standard quand son poids est $(1,1,\ldots ,1)$.

Tableau de Young gauche

Les cellules hachurées forment un diagramme de Young de forme gauche $(5,4,4,1)/(4,3,2)$, (notation française).

Tableau de Young gauche de forme $(5,4,2,2)/(2,1)$, (notation anglaise)

Une forme gauche est un couple $(\lambda ,\mu )$ de partitions tel que le diagramme de Young de la partition $\lambda$ contient le diagramme de Young de la partition $\mu$; ceci signifie que si $\lambda =(\lambda _{1},\lambda _{2},\ldots )$ et $\mu =(\mu _{1},\mu _{2},\ldots )$, alors $\lambda _{i}\geq \mu _{i}$ pour tout $i$. Une forme gauche est notée $\lambda /\mu$ ou $\lambda \setminus \mu$. Le diagramme gauche d'une forme gauche est la différence ensembliste des diagrammes de Young de $\lambda$ et de $\mu$ : il contient les cases qui sont dans le diagramme de $\lambda$ et pas dans le diagramme de $\mu$. Un tableau de Young gauche est obtenu en remplissant les cases du diagramme gauche correspondant. À nouveau, un tableau est semi-standard si les entrées sont strictement croissantes en colonne, et croissantes au sens large en ligne. Si de plus, tous les entiers de 1 au nombre de cellules apparaissent exactement une fois, le tableau est standard.

La forme gauche d'un diagramme de Young gauche ne peut pas toujours être déterminée à partir de l'ensemble de cellules du diagramme. Par exemple, si $\lambda =(5,4,2,1)$ et $\mu =(5,3,2,1)$, le diagramme gauche de forme $\lambda /\mu$ consiste en une seule cellule en position $(2,4)$. Mais cette cellule peut être obtenue d'une infinité d'autres façons, par exemple en allongeant la première ligne des deux formes, ou en ajoutant d'autres lignes identiques. De même, si un diagramme est composé de plusieurs parties non connexes, il peut être obtenue à partir de plusieurs formes différentes.

Tout tableau semi-standard gauche $T$ de forme $\lambda /\mu$ à entrées positives détermine une suite de partitions (ou de diagrammes de Young) comme suit : on commence avec $\mu$; à la $i$-ème étape, on prend comme partition celle dont le diagramme est obtenu à partir de $\mu$ en ajoutant toutes les cellules de $T$ qui contiennent une valeur $\leq i$; la partition finale est la partition $\lambda$. Toute paire consécutive de diagrammes de cette suite définit une forme gauche dont le diagramme contient au plus une entrée dans chaque colonne (parce que les entrées sont croissantes en colonne). De telles formes sont appelées bandes horizontales (horizontal strips en anglais). Cette suite de partitions détermine entièrement $T$.

Extension

Tableau de Young de forme (7, 6, 4, 2). Le mot correspondant est 6845562233571112444.

Au lieu de prendre les valeurs d'un tableau de Young dans les entiers, on les prend dans un alphabet quelconque, totalement ordonné. Lorsque l'on lit successivement les lignes d'un tableau de Young semi-standard, on obtient une suite de mots croissants au sens large sur cet alphabet. Chaque mot $x=x_{1}\cdots x_{r}$ de cette suite domine le suivant $y=y_{1}\cdots y_{s}$ dans le sens que $r\leqslant s$ et de plus $x_{i}<y_{i}$ pour $1\leqslant i\leqslant r$. Pour le diagramme de Young de la partition (3,3,1), les mots des lignes sont $4\,234\,122$, et chacune domine la suivante. Le produit des mots de lignes est parfois lui-même appelé tableau. Dans notre exemple, c'est le mot $4234122$. La correspondance entre mots et tableau semi-standard est bijective : pour décoder le mot, il suffit à chaque fois de prendre le préfixe le plus long qui est croissant au sens large. Dans le tableau ci-contre de forme $(7,6,4,2)$, le mot-tableau $6845562233571112444$ se factorise en lignes dont chacune domine la suivante.

Propriétés combinatoires

Algorithme de Schensted

L'algorithme de Schensted est un algorithme qui permet d'insérer un entier dans un tableau semi-standard ou standard, de manière à obtenir un nouveau tableau du même type. Cet algorithme permet :

• de munir l'ensemble des tableaux d'une loi de composition interne, en insérant successivement les éléments d'un tableau dans un autre.
• d'établir une bijection entre permutations, et plus généralement suites d'entiers positifs et paires de tableaux de Young standard (resp. semi-standard) $(P,Q)$ de même forme, connue sous le nom de correspondance de Robinson-Schensted-Knuth.
• d'induire une relation d'équivalence sur l'ensemble des suites finies d'entiers positifs. Deux mots sont équivalents si dans la correspondance de Robinson-Schensted, ils ont même tableau P.

Une construction géométrique de la correspondance de Robinson-Schensted entre permutations et paires de tableaux de Young standard de même forme a été donnée par Viennot.

Relations de Knuth

À partir de l'étude de cette relation d'équivalence sur les mots de longueur 3, Donald Knuth a défini des règles de réécriture sur l'ensemble des mots sur $[m]$. Ces règles de réécriture induisent également une relation d'équivalence, et Knuth a démontré qu'elle coïncide avec la relation de Schensted. Une conséquence importante de ce théorème est que la loi de composition qui découle de l'algorithme de Schensted possède toutes les propriétés requises pour donner à l'ensemble des tableaux une structure de monoïde : le monoïde plaxique.

Formule des équerres

Longueurs des équerres pour la partition de 10=5+4+1.

La formule des équerres (hook-length formula en anglais) est une formule qui permet de calculer le nombre de tableaux de Young standard de forme $\lambda$ donnée. Ce nombre est important, car le nombre de tableaux de Young standard de forme donnée est égal à la dimension de la représentation irréductible du groupe symétrique $S_{n}$ correspondant à une partition $\lambda$ de $n$.

L'équerre associée à une cellule $x$ du diagramme de Ferrers $Y(\lambda )$ de forme $\lambda$ est composé de cette cellule, et de toutes les cellules à droite et en dessous (dans la notation anglaise), respectivement à droite et au-dessus (dans la notation française) de la cellule $x$. La longueur de l'équerre $h(x)$ (en anglais hook-length) est le nombre de cellules composant l'équerre. Dans l'exemple de la partition $\lambda =(5,4,1)$, la cellule en haut à gauche a 5 cellules sur la même ligne et 3 sur la même colonne. Sa longueur d'équerre est donc 7.

On note $f^{\lambda }$ le nombre de tableaux de Young standard de forme $\lambda$, pour une partition de $n$.

Formule des équerres — Soit $f^{\lambda }$ le nombre de tableaux de Young standard de forme $\lambda$ pour une partition de $n$. Alors on a

$f^{\lambda }={\frac {n!}{\prod _{x\in Y(\lambda )}h(x)}}$.

La figure ci-contre donne les longueurs des équerres pour la partition $\lambda =(5,4,1)$. On obtient

$f^{\lambda }={\frac {10!}{7\cdot 5\cdot 4\cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot 1}}=288.$

Il y a donc 288 tableaux de Young standard de cette forme, et la représentation irréductible du groupe symétrique S₁₀ correspondante à cette partition est donc de dimension 288.

La formule des équerres est aussi appelée le théorème de Frame-Robinson-Thrall d'après les auteurs d'une preuve. Une preuve combinatoire, utilisant le jeu de taquin de Schützenberger a été donnée par Novelli, Pak et Stoyanovskii. En fait, de nombreuses preuves ont été données, parmi lesquelles d'autres preuves par bijection. La preuve de Novelli, Pak et Stoyanovskii est considérée par Krattenthaler comme la plus naturelle : « The bijection presented in the paper under review must be considered as the natural hook bijection ». Les livres de référence, comme Sagan 2001 ou Fulton 1997, contiennent des preuves. Une démonstration élémentaire et détaillée, par Jason Bandlow, existe en ligne.

Formule de la somme des carrés

Une formule proche de la formule des équerres est la suivante :

Somme des carrés — Soit $n$ un entier. On a :

$\sum _{\lambda }(f^{\lambda })^{2}=n\,!$,

où la somme est sur toutes les partitions $\lambda$ de $n$, et $f^{\lambda }$ est le nombre de tableaux de Young standard de forme $\lambda$.

Par exemple, pour les partitions (3), (2,1) et (1,1,1) de l'entier 3, il y a respectivement 1, 2 et 1 tableau(x) de Young standard de cette forme, d'où le total 1+4+1=6=3!. Une démonstration de cette formule se fait bien au moyen des treillis de Young.

Survol des applications

Les tableaux de Young ont de nombreuses applications en combinatoire, en théorie des représentations et en géométrie algébrique. Diverses façons de compter les tableaux de Young ont été explorées, et ont conduit à la définition et à des identités sur les polynômes de Schur. De nombreux algorithmes ont été développés, y compris le jeu de taquin de Schützenberger, la correspondance de Robinson-Schensted-Knuth, ou la construction géométrique de Viennot. Lascoux et Schützenberger ont introduit un produit associatif sur l'ensemble des tableaux de Young semi-standard qui muni cet ensemble d'une structure de monoïde, appelé le monoïde plaxique.

En théorie des représentations, les tableaux de Young standard de taille $k$ décrivent des bases des représentations irréductibles du groupe symétrique sur $k$ lettres. Les bases monomiales standard d'une représentation irréductible de dimension finie du groupe général linéaire ${\text{GL}}_{n}$ sont paramétrées par l'ensemble des tableaux de Young semi-standard de forme fixée sur l'alphabet $\{1,2,\ldots ,n\}$. Ceci a des conséquences importantes en théorie des invariants. La règle de Littlewood-Richardson qui décrit, entre autres, la décomposition du produit tensoriel de représentations irréductibles de ${\text{GL}}_{n}$ en composantes irréductibles est formule en termes de tableaux de Young gauches.

Les applications en géométrie algébrique se concentrent sur le calcul de Schubert, sur les grassmanniennes et les variétés de drapeaux. Certaines classes de cohomologie importantes peuvent être représentées par des polynômes de Schubert et décrites en termes de tableaux de Young.

Applications aux représentations des groupes

Représentation de GL(E)

Si E est un ℂ-espace vectoriel de dimension m, et λ une partition, on définit le module de Schur E^λ comme étant le ℂ-espace vectoriel dont une base est formée par l'ensemble des tableaux de Young de forme λ et à valeur dans [m]. Sachant qu'il est possible d'identifier un tableau de Young à valeurs dans [m] à un polynôme de ℂ[X_i,j|1≤i,j≤m], il existe une action naturelle de GL(E) sur les tableaux de Young par simple multiplication matricielle. Les modules de Schur sont donc des représentations de GL(E). On peut montrer que toute représentation polynomiale irréductible de GL(E) est isomorphe à un unique module de Schur.

Fonctions symétriques

Les caractères des modules de Schur (en tant que représentations de GL(E)) sont des polynômes symétriques appelés polynômes de Schur, d'après le mathématicien russe Issai Schur. Les tableaux de Young fournissent un moyen élégant pour exprimer ces polynômes. Par ailleurs, il existe une règle purement combinatoire qui fait appel aux tableaux de Young, et qui permet de décomposer le produit de deux polynômes de Schur. Ceci implique en particulier que les tableaux permettent de décomposer le produit tensoriel de deux représentations irréductibles de GL(E) en somme directe de représentations irréductibles.

Bibliographie

• (en) William Fulton, Young tableaux, Cambridge University Press, coll. « London Mathematical Society Student Texts » (n^o 35), 1997 (ISBN 978-0-521-56144-0 et 978-0-521-56724-4, MR 1464693)
• (en) Donald E. Knuth, « Permutations, matrices, and generalized Young tableaux », Pacific Journal of Mathematics, vol. 34,‎ 1970, p. 709–727 (ISSN 0030-8730, MR 0272654, lire en ligne)
• (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, 1998, 2^e éd. [détail de l’édition]
• (en) Bruce E. Sagan, The Symmetric Group : Representations, Combinatorial Algorithms, and Symmetric Functions, New York/Berlin/Heidelberg etc., Springer, coll. « GTM » (n^o 203), 2001, 2^e éd., 238 p. (ISBN 0-387-95067-2)
• (en) Richard P. Stanley, Enumerative Combinatorics, vol. 2 [détail des éditions] (présentation en ligne)