Tableau de Young

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

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.

Définition[modifier | modifier le code]

Diagramme de Young[modifier | modifier le code]

Diagramme de Young de forme (5, 4, 1), notation anglaise
Diagramme de Young de forme (5, 4, 1), notation française

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 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 nombres 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[1]. La notation anglaise correspond aux matrices, la notation française aux coordonnées cartésiennes.

Tableau de Young[modifier | modifier le code]

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, 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. Les entrées sont alors strictement croissantes dans les lignes et dans les colonnes, et . 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[modifier | modifier le code]

Les cellules hachures 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\le\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 table 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 \le 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[2].

Extension[modifier | modifier le code]

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

Au lieu de prendre les valeurs d'un tableau de Young dans les entiers, on les prend dans un alphabet quelconque, totalement ordonné[3]. 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\le s et de plus x_i< y_i pour 1\le i\le 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[4]. 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 684556223357111444 se factorise en lignes dont chacune domine la suivante.

Propriétés combinatoires[modifier | modifier le code]

Algorithme de Schensted[modifier | modifier le code]

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

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

Article détaillé : Monoïde plaxique.

Formule des équerres[modifier | modifier le code]

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\cdot5\cdot 4 \cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot1} = 288.

Il y a donc 288 tableaux de Young standard de cette forme, et il y a autant de représentations irréductibles du groupe symétrique S_{10} correspondant à cette partition.

La formule des équerres est aussi appelée le théorème de Frame-Robinson-Thrall d'après les auteurs d'une preuve[5]. Une preuve combinatoire, utilisant le jeu de taquin de Schützenberger a été donnée par Novelli, Pak et Stoyanovskii[6]. En fait, de nombreuses preuves ont été données, parmi lesquelles d'autres preuves bijectives. 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 »[7]. 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[8].

Formule de la somme des carrés[modifier | modifier le code]

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

Les tableaux de Young ont de nombreuses application 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 (en), 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 (en) et décrites en termes de tableaux de Young.

Applications au représentations des groupes[modifier | modifier le code]

Représentations du groupe symétrique[modifier | modifier le code]

Représentation de GL(E)[modifier | modifier le code]

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 ℂ[Xi,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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

  1. Dans (Macdonald, 1979, p. 2), Macdonald recommande aux lecteurs qui préfèrent la notation française de lire ce livre « du bas vers le haut dans un miroir ».
  2. Et on peut définir les tableaux semi-standard gauche comme de telles séquences ; c'est ainsi que procède Macdonald (Macdonald, 1979, p. 4)
  3. Lascoux, Leclerc & Thibon, 2002
  4. Lascoux, Leclerc & Thibon, 2002, p. 166
  5. Frame, Robinson et Thrall 1954
  6. Novelli, Pak et Stoyanovskii 1997
  7. Revue de l’article de Novelli, Pak et Stoyanovskii dans MathSciNet. Accès limité.
  8. Jason Bandlow, « An elementary proof of the hook formula », The Electronic Journal for Combinatorics, vol. 15,‎ 2008 (lire en ligne).

Bibliographie[modifier | modifier le code]