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