Pictures

A class of bijections (cf. Bijection) between subsets of $ \mathbf Z \times \mathbf Z $, namely skew diagrams. A skew diagram is a finite subset $ S \subset \mathbf Z \times \mathbf Z $ such that $ x \leq y \leq z $ with $ x,z \in S $ implies $ y \in S $, where "≤" is the coordinatewise partial ordering of $ \mathbf Z \times \mathbf Z $; a typical skew diagram is the difference $ \lambda \setminus \mu $ of two Young diagrams (cf. Young diagram) $ \lambda, \mu $ with $ \mu \subset \lambda $. The definition of pictures also uses another partial ordering "≤" on $ \mathbf Z \times \mathbf Z $, given by

$$ ( i,j ) \leq _ \swarrow ( i ^ \prime ,j ^ \prime ) \iff i \geq i ^ \prime \wedge j \leq j ^ \prime $$

(sometimes the opposite ordering is used instead); a bijection $ f $ between two skew diagrams is a picture if $ x \leq y $ implies $ f ( x ) \leq _ \swarrow f ( y ) $ and $ u \leq v $ implies $ f ^ {- 1 } ( u ) \leq _ \swarrow f ^ {- 1 } ( v ) $. The set of all pictures has various symmetries, among which $ f \left\rightarrow f ^ {- 1 } $.

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 $ \mathbf N $ or $ \{ 0,1 \} $ 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 $ \chi $, $ \psi $, the number of pictures $ \chi \rightarrow \psi $ is equal to the intertwining number of representations $ V _ \chi $ and $ V _ \psi $ of $ S _ {n} $, or of $ { \mathop{\rm GL} } _ {m} $, see [a5]. In particular, the number of pictures from $ \lambda \setminus \mu $ to $ \nu $, for Young diagrams $ \lambda $, $ \mu $, $ \nu $, is the multiplicity of the irreducible representation $ V _ \lambda $ of $ { \mathop{\rm GL} } _ {m} $ in $ V _ \mu \otimes V _ \nu $; this is essentially the Littlewood–Richardson rule.

There is a natural bijection between pictures $ f : \chi \rightarrow \psi $, for arbitrary skew shapes $ \chi $, $ \psi $, and pairs of pictures $ p : \lambda \rightarrow \psi $ and $ q : \chi \rightarrow \lambda $, for some Young diagram $ \lambda $. 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 $ V ^ {\otimes n } $ 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 $ P $- symbol in the ordinary Robinson–Schensted correspondence, the picture $ p $ can not only be computed from $ f $ by an insertion procedure, but also by using the jeu de taquin (see [a4]), to gradually transform the domain $ \chi $ into a Young diagram $ \lambda $. By the symmetry $ f \leftrightarrow f ^ {- 1 } $, the picture $ q $ can also be computed by the jeu de taquin at the image side, to transform the image $ \psi $ into $ \lambda $. 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