Construction géométrique de Viennot

On considère une permutation ${\displaystyle \sigma }$ sur les entiers de 1 à ${\displaystyle n}$, écrite dans la notation fonctionnelle :

${\displaystyle \sigma ={\begin{pmatrix}1&2&\cdots &n\\a_{1}&a_{2}&\cdots &a_{n}\end{pmatrix}},}$

Si on applique la correspondance de Robinson–Schensted à cette permutation, on obtient une paire de tableaux de Young standard ${\displaystyle P}$ et ${\displaystyle Q}$ de même forme. Le tableau ${\displaystyle P}$ est obtenu en réalisant une suite d'insertions, et le tableau ${\displaystyle Q}$ mémorise dans quel ordre les cellules ont été remplies.

La construction de Viennot commence par placer les points ${\displaystyle (i,a_{i})}$ dans le plan. On imagine une source de lumière placée à l'origine qui provoque des ombres vers le haut et vers la droite (l'ombre due au point ${\displaystyle (i,a_{i})}$ est formée des points dont les deux coordonnées sont supérieures ou égales à celles de ${\displaystyle (i,a_{i})}$). Ceci permet de considérer l'ensemble des points de la permutation qui sont éclairés parce qu'ils ne sont pas dans l'ombre d'un autre point. La frontière de leurs ombres forme la première ligne d'ombre. On enlève ces points et on répète cette procédure. On obtient ainsi une suite de lignes d'ombre. Viennot a observé que ces lignes d'ombre codent une ligne de ${\displaystyle P}$ et ${\displaystyle Q}$. Chaque ligne d'ombre fournit, par son abscisse minimale, une entrée dans ${\displaystyle P}$, et par son ordonnée minimale, une entrée dans ${\displaystyle Q}$. On répète ensuite la construction, en partant cette fois-ci comme points les sommets des intersections de cônes d'ombre non étiquetés. Ceci donne les lignes suivantes de P et Q.

On considère la permutation :

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&4&5&6&7&8\\3&8&1&2&4&7&5&6\end{pmatrix}}.}$

La construction de Viennot se déroule comme suit :

En plus de son intérêt intrinsèque, la construction géométrique de Viennot peut servir pour prouver que si ${\displaystyle (P,Q)}$ est la paire de tableaux associée à ${\displaystyle \sigma }$ dans la correspondance de Robinson–Schensted, alors la paire ${\displaystyle (Q,P)}$ est associée à la permutation inverse ${\displaystyle \sigma ^{-1}}$. En effet, remplacer ${\displaystyle \sigma }$ par ${\displaystyle \sigma ^{-1}}$ correspond à une symétrie autour de l'axe ${\displaystyle y=x}$, et ceci échange précisément le rôle de ${\displaystyle P}$ et de ${\displaystyle Q}$.