Pictures
A class of bijections (cf. Bijection) between subsets of , namely skew diagrams. A skew diagram is a finite subset
such that
with
implies
, where "≤" is the coordinatewise partial ordering of
; a typical skew diagram is the difference
of two Young diagrams (cf. Young diagram)
with
. The definition of pictures also uses another partial ordering "≤" on
, given by
![]() |
(sometimes the opposite ordering is used instead); a bijection between two skew diagrams is a picture if
implies
and
implies
. The set of all pictures has various symmetries, among which
.
When domain and image are fixed to certain shapes, pictures become equivalent to many other combinatorial concepts, such as permutations, (semi-) standard Young tableaux, skew tableaux, Littlewood–Richardson fillings, and matrices over or
with prescribed row and column sums. On the other hand, any picture gives rise to a semi-standard skew tableau by projecting its images onto their first coordinate. For any skew diagrams
,
, the number of pictures
is equal to the intertwining number of representations
and
of
, or of
, see [a5]. In particular, the number of pictures from
to
, for Young diagrams
,
,
, is the multiplicity of the irreducible representation
of
in
; this is essentially the Littlewood–Richardson rule.
There is a natural bijection between pictures , for arbitrary skew shapes
,
, and pairs of pictures
and
, for some Young diagram
. This is a generalization of the Robinson–Schensted correspondence, and it agrees with the intertwining number interpretation. It also gives a decomposition of skew Schur polynomials into ordinary Schur polynomials, generalizing the decomposition of the character of
mentioned in Robinson–Schensted correspondence, and thereby provides a proof of the Littlewood–Richardson rule; this is closely related to the reason that correspondence was originally introduced in [a3]. Like the
-symbol in the ordinary Robinson–Schensted correspondence, the picture
can not only be computed from
by an insertion procedure, but also by using the jeu de taquin (see [a4]), to gradually transform the domain
into a Young diagram
. By the symmetry
, the picture
can also be computed by the jeu de taquin at the image side, to transform the image
into
. The steps of these two forms of the jeu de taquin commute with each other, and this provides a key to many properties of the Robinson–Schensted correspondence [a2].
References
[a1] | S. Fomin, C. Greene, "A Littlewood–Richardson miscellany" European J. Combinatorics , 14 (1993) pp. 191–212 |
[a2] | M.A.A. van Leeuwen, "Tableau algorithms defined naturally for pictures" Discrete Math. , 157 (1996) pp. 321–362 |
[a3] | G. de B. Robinson, "On the representations of the symmetric group" Amer. J. Math. , 60 (1938) pp. 745–760 |
[a4] | M.P. Schützenberger, "La correspondance de Robinson" D. Foata (ed.) , Combinatoire et Représentation du Groupe Symétrique , Lecture Notes in Mathematics , 579 , Springer (1976) pp. 59–113 |
[a5] | A.V. Zelevinsky, "A generalisation of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence" J. Algebra , 69 (1981) pp. 82–94 |
Pictures. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Pictures&oldid=18156