Construction géométrique de Viennot

En mathématiques, la construction géométrique de Viennot donne une interprétation géométrique de la correspondance de Robinson-Schensted en termes de lignes d'ombre.

La construction

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

$\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 $P$ et $Q$ de même forme. Le tableau $P$ est obtenu en réalisant une suite d'insertions, et le tableau $Q$ mémorise dans quel ordre les cellules ont été remplies.

La construction de Viennot commence par placer les points $(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 $(i,a_{i})$ est formée des points dont les deux coordonnées sont supérieures ou égales à celles de $(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 $P$ et $Q$. Chaque ligne d'ombre fournit, par son abscisse minimale, une entrée dans $P$, et par son ordonnée minimale, une entrée dans $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.

Animation

On considère la permutation :

$\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 :

Application

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

Notes et références

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

Bibliographie

• Gérard Viennot, « Une forme géométrique de la correspondance de Robinson-Schensted », dans Dominique Foata (éditeur), Combinatoire et représentation du groupe symétrique : Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976, Springer, coll. « Lecture Notes in Math. » (n^o 579), 1977 (ISBN 978-3-540-08143-2), p. 29–58
• (en) Bruce E. Sagan, The Symmetric Group : Representations, combinatorial algorithms, and symmetric functions, New York/Berlin/Heidelberg etc., Springer-Verlag, coll. « Graduate Texts in Mathematics » (n^o 203), 2001, 2^e éd., 238 p. (ISBN 0-387-95067-2, MR 1824028, lire en ligne)
• Marcel-Paul Schützenberger, « La correspondance de Robinson », dans Dominique Foata (éditeur), Combinatoire et représentation du groupe symétrique : Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976, Springer, coll. « Lecture Notes in Math. » (n^o 579), 1977 (ISBN 978-3-540-08143-2, DOI 10.1007/BFb0090012), p. 59–113
• (en) Richard P. Stanley, Enumerative Combinatorics, vol. 2 [détail des éditions] (présentation en ligne)

Voir aussi

• Monoïde plaxique
• Jeu de taquin de Schützenberger