Jean-François Mertens: Difference between revisions
No edit summary |
en>Mr. Granger Repairing links to disambiguation pages - You can help! |
||
Line 1: | Line 1: | ||
In mathematics, '''Viennot's geometric construction''' (named after Xavier Gérard Viennot) gives a diagrammatic interpretation of the [[Robinson–Schensted correspondence]] in terms of '''shadow lines'''. | |||
==The construction== | |||
Starting with a permutation <math> \sigma \in S_n </math>, written in two-line notation, say: | |||
: <math> \sigma = \begin{pmatrix} | |||
1 & 2 & \cdots & n \\ | |||
\sigma_1 & \sigma_2 & \cdots & \sigma_n | |||
\end{pmatrix},</math> | |||
one can apply the Robinson–Schensted correspondence to this permutation, yielding two [[Young tableau|standard Young tableaux]] of the same shape, ''P'' and ''Q''. ''P'' is obtained by performing a sequence of insertions, and ''Q'' is the recording tableau, indicating in which order the boxes were filled. | |||
Viennot's construction starts by plotting the points <math> (i, \sigma_i) </math> in the plane, and imagining there is a light that shines from the origin, casting shadows straight up and to the right. This allows consideration of the points which are not shadowed by any other point; the boundary of their shadows then forms the first shadow line. Removing these points and repeating the procedure, one obtains all the shadow lines for this permutation. Viennot's insight is then that these shadow lines read off the first rows of ''P'' and ''Q'' (in fact, even more than that; these shadow lines form a "timeline", indicating which elements formed the first rows of ''P'' and ''Q'' after the successive insertions). One can then repeat the construction, using as new points the previous unlabelled corners, which allows to read off the other rows of ''P'' and ''Q''. | |||
==Animation== | |||
For example consider the permutation | |||
: <math> \sigma = \begin{pmatrix} | |||
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ | |||
3 & 8 & 1 & 2 & 4 & 7 & 5 & 6 | |||
\end{pmatrix}. | |||
</math> | |||
Then Viennot's construction goes as follows: | |||
[[Image:ViennotAnimation.gif]] | |||
==Applications== | |||
One can use Viennot's geometric construction to prove that if <math>\sigma</math> corresponds to the pair of tableaux ''P'',''Q'' under the Robinson–Schensted correspondence, then <math>\sigma^{-1}</math> corresponds to the switched pair ''Q'',''P''. Indeed, taking <math>\sigma</math> to <math>\sigma^{-1}</math> reflects Viennot's construction in the <math>y=x</math>-axis, and this precisely switches the roles of ''P'' and ''Q''. | |||
==See also== | |||
* [[Plactic monoid]] | |||
* [[Jeu de taquin]] | |||
==References== | |||
* [[Bruce Sagan|Bruce E. Sagan]]. ''The Symmetric Group''. Springer, 2001. | |||
[[Category:Algebraic combinatorics]] |
Revision as of 01:45, 1 February 2014
In mathematics, Viennot's geometric construction (named after Xavier Gérard Viennot) gives a diagrammatic interpretation of the Robinson–Schensted correspondence in terms of shadow lines.
The construction
Starting with a permutation , written in two-line notation, say:
one can apply the Robinson–Schensted correspondence to this permutation, yielding two standard Young tableaux of the same shape, P and Q. P is obtained by performing a sequence of insertions, and Q is the recording tableau, indicating in which order the boxes were filled.
Viennot's construction starts by plotting the points in the plane, and imagining there is a light that shines from the origin, casting shadows straight up and to the right. This allows consideration of the points which are not shadowed by any other point; the boundary of their shadows then forms the first shadow line. Removing these points and repeating the procedure, one obtains all the shadow lines for this permutation. Viennot's insight is then that these shadow lines read off the first rows of P and Q (in fact, even more than that; these shadow lines form a "timeline", indicating which elements formed the first rows of P and Q after the successive insertions). One can then repeat the construction, using as new points the previous unlabelled corners, which allows to read off the other rows of P and Q.
Animation
For example consider the permutation
Then Viennot's construction goes as follows:
Applications
One can use Viennot's geometric construction to prove that if corresponds to the pair of tableaux P,Q under the Robinson–Schensted correspondence, then corresponds to the switched pair Q,P. Indeed, taking to reflects Viennot's construction in the -axis, and this precisely switches the roles of P and Q.
See also
References
- Bruce E. Sagan. The Symmetric Group. Springer, 2001.