# 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
How to Cite This Entry:
Pictures. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Pictures&oldid=48180
This article was adapted from an original article by M.A.A. van Leeuwen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article