Treillis de Young

En mathématiques, et notamment en combinatoire, le treillis de Young est l'ensemble partiellement ordonné composé de toutes les partitions d'entiers. Cet ensemble est un treillis. Il est nommé ainsi d'après Alfred Young qui, dans une série d'articles intitulés On quantitative substitutional analysis a développé la théorie des représentations du groupe symétrique. Dans la théorie de Young, les objets appelés maintenant diagrammes de Young ou diagrammes de Ferrers et l'ordre partiels définis sur eux jouent un rôle central. Le treillis de Young occupe une place éminente en combinatoire algébrique, et est l'exemple le plus simple d'ensemble ordonné différentiel (en) au sens de Stanley 1988. Il est aussi étroitement lié à la base canonique des algèbres de Lie affines.

Le diagramme de Hasse du treillis de Young.

Définition

Le treillis de Young est l'ensemble partiellement ordonné formé de toutes les partitions d'entiers, ordonnées par l'inclusion de leur diagramme de Young (ou diagramme de Ferrers).

Signification

L'application traditionnelle du treillis de Young est la description des représentations irréductibles du groupe symétrique $S_{n}$ pour tout $n$ et de leurs propriétés de branchement en caractéristique zéro. Les classes d'équivalences de représentations irréductibles peuvent être paramétrées par des partitions ou diagrammes de Young. La restriction de $S_{n+1}$ à $S_{n}$ est sans multiplicité, et la représentation de $S_{n}$ avec partition $p$ est contenue dans la représentation de $S_{n}$ avec partition $q$ si et seulement si $q$ couvre $p$ dans le treillis de Young. En itérant cette procédure, on arrive à la base semi-canonique de Young dans la représentation de $S_{n}$ avec partition $p$ qui est indexée par les tableaux de Young standard de forme $p$.

Propriétés

Soit $Y$ l'ensemble ordonné de toutes les partitions.

• L'ensemble ordonné $Y$ est un ensemble gradué : le plus petit élément est l'ensemble vide qui est l'unique partition du nombre zéro. Chaque partition a un rang. Les partitions de l'entier $n$ ont toutes rang $n$. Ceci signifie que les rangs de deux partitions comparables sont ordonnés comme les partitions, et il existe au moins une partition intermédiaire pour tout rang intermédiaire.
• L'ensemble ordonné $Y$ est un treillis. Les bornes inférieure et supérieure sont données par l’intersection et la réunion de leurs diagrammes de Young respectifs. Comme l'ensemble est un treillis dans lequel les bornes inférieures et supérieures sont représentées par des intersections et réunions, le treillis est distributif.
• Si une partition $p$ couvre $k$ éléments du treillis de Young pour un certain $k$, alors il est lui-même couvert par $k+1$ éléments. Les partitions couvertes par $p$ sont obtenues en supprimant une « coin » du diagramme, c'est-à-dire une cellule qui termine une ligne et une colonne. Toutes les partitions qui couvrent $p$ sont obtenues en ajoutant une cellule qui est un « coin dual » : c'est une cellule nouvelle qui est la première cellule nouvelle dans sa ligne ou et sa colonne. En fait, une telle cellule existe pour la première ligne, et pour tout autre coin dual, il existe un coin dans coin dans la ligne précédente, d'où la différence de 1 entre les partitions qui couvrent et les partitions couvertes. Par exemple, la partition (2,1,1) de l'entier 4 possède deux coins, l'un dans la première ligne et l'un dans la troisième, ce qui donne les deux partitions (1,1,1) et (2,1). La partition (2,1,1) elle-même possède trois coins duaux, dans la première, la deuxième et la quatrième ligne.
• Si deux partitions distinctes $p$ et $q$ couvrent chacune $k$ éléments de $Y$, alors $k=0$ ou $k=1$, et $p$ et $q$ sont couvertes par $k$ éléments. Autrement dit : deux partitions ne peuvent couvrir qu'une seule même partition, car leurs diagrammes respectifs contiennent chacun exactement une cellule qui ne figure pas dans l’autre. Dans ce cas, il existe une quatrième partition qui couvre ces deux partitions et qui est la réunion de leur diagrammes.
• Les chaînes saturées (c'est-à-dire les suites de partitions dont chacune couvre la précédente) entre la partition vide et une partition $p$ sont en bijection naturelle avec les tableaux de Young standard de forme $p$ : les cellules du diagramme sont numérotées dans l'ordre dans lequel elles sont ajoutées. Plus généralement, les chaînes saturées entre $q$ et $p$ sont en bijection naturelle avec les tableaux de Young gauches de forme $p/q$.
• La fonction de Möbius du treillis de Young prend les valeurs 0, +1, ou -1. Elle est donnée par la formule

$\mu (q,p)={\begin{cases}(-1)^{|p|-|q|}&{\text{si le diagramme gauche }}p/q{\text{ est l'union de cellules sans côté en commun}},\\[10pt]0&{\text{sinon}}.\end{cases}}$

Symétrie diédrale

Ce dessin inhabituel d'une partie du treillis de Young montre une symétrie axiale et une symétrie de rotation d'ordre 5, donc une symétrie diédrale.

La représentation picturale usuelle du treillis de Young est un diagramme de Hasse où les éléments de même rank sont tracés à la même hauteur. Suter, en 2002, a montré qu'un dessin différent pouvait faire apparaître des symétries inattendues.

La partition

$n+\cdots +3+2+1$

du $n$^e nombre triangulaire a un diagramme de Ferrers en escalier. Les plus grandes partitions contenues dans cette partition et dont le diagramme de Ferrers est un rectangle sont les suivantes :

$\underbrace {1+\cdots +1} _{n{\text{ termes}}}\quad \underbrace {2+\cdots +2} _{n-1{\text{ termes}}}\quad \underbrace {3+\cdots +3} _{n-2{\text{ termes}}}\qquad \cdots \quad \underbrace {{}\ n\ {}} _{1{\text{ terme}}}$

Par exemple, pour $n=4$, les éléments rectangulaires maximaux sont :

1 + 1 + 1 + 1

2 + 2 + 2

3 + 3

4

Les partitions rectangulaires ne couvrent qu'un seul élément, puisqu'elles possèdent un seul coin. Suter montre que l'ensemble des éléments en-dessous de ces partitions a non seulement une symétrie latérale à laquelle on s'attend dans le treillis de Young, mais aussi une symétrie de rotation : le groupe des rotations d'ordre $n+1$ agit sur cet ensemble. Comme il possède à la fois une symétrie axiale et une symétrie de rotation, il a une symétrie diédrale : le groupe diédral d'ordre $n+1$ opère fidèlement sur cet ensemble. La taille de cet ensemble est $2^{n}$.

Dans le cas $n=4$ représenté dans la figure, c'est le groupe diédral $D_{5}$ qui opère fidèlement sur ce sous-ensemble du treillis de Young.

Formule de la somme des carrés

La considération du treillis de Young permet une démonstration simple d'une des formules étonnantes concernant les tableaux de Young, appelée parfois la « formule de la somme des carrés » (par exemple sum-of-squares formula chez Bruce Sagan). Pour le diagramme de Ferrers $\lambda$ d'une partition de $n$ donnée, notons $f^{\lambda }$ le nombre de tableaux de Young de forme $\lambda$. D'après les propriétés du treillis de Young énoncées plus haut, $f^{\lambda }$ est le nombre de chaînes de longueur $n$ de l'ensemble vide à $\lambda$. La formule annoncée est :

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

Pour établir cette formule, on considère l'espace vectoriel $\mathbb {C} Y$ des combinaisons linéaires formelles d'éléments de $Y$, et on définit sur cet espace deux opérateurs $D$ et $U$ (pour down et up) qui correspondent à la descente et la montée dans le treillis de Young, par :

$D(\lambda )=\sum \lambda ^{-},\qquad U(\lambda )=\sum \lambda ^{+}$,

où $\lambda ^{-}$ resp. $\lambda ^{+}$ parcourt l'ensemble des éléments couverts par $\lambda$ respectivement qui couvrent $\lambda$. Par exemple

$D\left({\begin{matrix}\bullet &\bullet &\bullet \\\bullet &\bullet &\end{matrix}}\right)={\begin{matrix}\bullet &\bullet \\\bullet &\bullet \end{matrix}}+{\begin{matrix}\bullet &\bullet &\bullet \\\bullet &&\end{matrix}}$

et

$U\left({\begin{matrix}\bullet &\bullet &\bullet \\\bullet &\bullet &\end{matrix}}\right)={\begin{matrix}\bullet &\bullet &\bullet &\bullet \\\bullet &\bullet &\end{matrix}}+{\begin{matrix}\bullet &\bullet &\bullet \\\bullet &\bullet &\bullet \end{matrix}}+{\begin{matrix}\bullet &\bullet &\bullet \\\bullet &\bullet &\\\bullet \end{matrix}}$

Nous avons constaté qu'il y a un élément de plus qui couvre un diagramme donné que d'éléments couverts. Il en résulte la formule

$DU-UD=I$

où $I$ est l'opérateur identité. En effet, on a

$DU(\lambda )=\sum \mu +(k+1)\lambda$,

où la somme est sur les éléments $\mu \neq \lambda$ qui sont couverts par un élément qui couvre aussi $\lambda$, et $k+1$ est le nombre d'éléments couvrant $\lambda$. De même, $UD(\lambda )=\sum \mu +k\lambda$, et en prenant la différence, on obtient la formule. Comme conséquence, on obtient pour $n>0$ :

$DU^{n}=nU^{n-1}+U^{n}D$.

C'est la formule précédente pour n=1, et par récurrence on a

$DU^{n+1}=(DU^{n})U=(nU^{n-1}+U^{n}D)U=nU^{n}+U^{n}(I+UD)=(n+1)U^{n}+U^{n+1}D$.

Le nombre de chaînes de longueur $n$ reliant un élément $\lambda$ donné à l'élément vide $\emptyset$ est $f^{\lambda }$. Il s'exprime par la formule

$D^{n}(\lambda )=f^{\lambda }\emptyset$.

Les éléments qu'on peut atteindre par des chaînes de longueur $n$ depuis l'élément vide $\emptyset$ est

$U^{n}(\emptyset )=\sum _{|\lambda |=n}f^{\lambda }\lambda$.

Il en résulte que

$D^{n}U^{n}(\emptyset )=\left(\sum _{|\lambda |=n}{\left(f^{\lambda }\right)}^{2}\right)\emptyset$.

Maintenant, on prouve que $D^{n}U^{n}(\emptyset )=n!\emptyset$ par récurrence sur $n$. On a

$D^{n}U^{n}(\emptyset )=D^{n-1}(DU^{n})(\emptyset )=D^{n-1}(nU^{n-1}+U^{n}D)(\emptyset )=nD^{n-1}U^{n-1}(\emptyset )+D^{n-1}U^{n}D(\emptyset )=n(n-1)!\emptyset +0$.

Ceci termine la démonstration.

Voir aussi

• treillis de Young-Fibonacci

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Young's lattice » (voir la liste des auteurs).

Références

• Kailash C. Misra et Tetsuji Miwa, « Crystal base for the basic representation of $U_{q}({\widehat {\mathfrak {sl}}}(n))$ », Communications in Mathematical Physics, vol. 134, n^o 1,‎ novembre 1990, p. 79-88 (DOI 10.1007/BF02102090)

• Bruce Sagan, The Symmetric Group : Representations, Combinatorial Algorithms, and Symmetric Functions, New York/Berlin/Heidelberg etc., Springer, coll. « Graduate Texts in Mathematics » (n^o 203), 2001, 2^e éd., 238 p. (ISBN 0-387-95067-2, lire en ligne), « Section 5.1. Young's Lattice and Differential Posets »
• Richard P. Stanley, « Differential Posets », Journal of the American Mathematical Society, vol. 1, n^o 4,‎ octobre 1988, p. 919 (DOI 10.2307/1990995)
• Ruedi Suter, « Young’s Lattice and Dihedral Symmetries », European Journal of Combinatorics, vol. 23, n^o 2,‎ février 2002, p. 233-238 (DOI 10.1006/eujc.2001.0541)