Namespaces
Variants
Actions

Difference between revisions of "Pictures"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
A class of bijections (cf. [[Bijection|Bijection]]) between subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101301.png" />, namely skew diagrams. A skew diagram is a finite subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101302.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101303.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101304.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101305.png" />, where  "≤"  is the coordinatewise partial ordering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101306.png" />; a typical skew diagram is the difference <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101307.png" /> of two Young diagrams (cf. [[Young diagram|Young diagram]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101308.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p1101309.png" />. The definition of pictures also uses another partial ordering  "≤"  on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013010.png" />, given by
+
<!--
 +
p1101301.png
 +
$#A+1 = 50 n = 0
 +
$#C+1 = 50 : ~/encyclopedia/old_files/data/P110/P.1100130 Pictures
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013011.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
(sometimes the opposite ordering is used instead); a bijection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013012.png" /> between two skew diagrams is a picture if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013013.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013015.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013016.png" />. The set of all pictures has various symmetries, among which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013017.png" />.
+
A class of bijections (cf. [[Bijection|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|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
  
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013018.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013019.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013021.png" />, the number of pictures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013022.png" /> is equal to the [[Intertwining number|intertwining number]] of representations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013024.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013025.png" />, or of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013026.png" />, see [[#References|[a5]]]. In particular, the number of pictures from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013027.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013028.png" />, for Young diagrams <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013031.png" />, is the multiplicity of the [[Irreducible representation|irreducible representation]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013032.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013033.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013034.png" />; this is essentially the Littlewood–Richardson rule.
+
$$
 +
( i,j ) \leq  _  \swarrow  ( i  ^  \prime  ,j  ^  \prime  ) \iff  i \geq  i  ^  \prime  \wedge j \leq  j  ^  \prime
 +
$$
  
There is a natural bijection between pictures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013035.png" />, for arbitrary skew shapes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013037.png" />, and pairs of pictures <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013039.png" />, for some Young diagram <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013040.png" />. This is a generalization of the [[Robinson–Schensted correspondence|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013041.png" /> mentioned in [[Robinson–Schensted correspondence|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 [[#References|[a3]]]. Like the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013042.png" />-symbol in the ordinary Robinson–Schensted correspondence, the picture <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013043.png" /> can not only be computed from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013044.png" /> by an insertion procedure, but also by using the [[Jeu de taquin|jeu de taquin]] (see [[#References|[a4]]]), to gradually transform the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013045.png" /> into a Young diagram <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013046.png" />. By the symmetry <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013047.png" />, the picture <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013048.png" /> can also be computed by the jeu de taquin at the image side, to transform the image <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013049.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p110/p110130/p11013050.png" />. 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 [[#References|[a2]]].
+
(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|intertwining number]] of representations  $  V _  \chi  $
 +
and  $  V _  \psi  $
 +
of  $  S _ {n} $,
 +
or of  $  { \mathop{\rm GL} } _ {m} $,
 +
see [[#References|[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|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|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|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 [[#References|[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|jeu de taquin]] (see [[#References|[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 [[#References|[a2]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Fomin,  C. Greene,  "A Littlewood–Richardson miscellany"  ''European J. Combinatorics'' , '''14'''  (1993)  pp. 191–212</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.A.A. van Leeuwen,  "Tableau algorithms defined naturally for pictures"  ''Discrete Math.'' , '''157'''  (1996)  pp. 321–362</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. de B. Robinson,  "On the representations of the symmetric group"  ''Amer. J. Math.'' , '''60'''  (1938)  pp. 745–760</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.V. Zelevinsky,  "A generalisation of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence"  ''J. Algebra'' , '''69'''  (1981)  pp. 82–94</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S. Fomin,  C. Greene,  "A Littlewood–Richardson miscellany"  ''European J. Combinatorics'' , '''14'''  (1993)  pp. 191–212</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.A.A. van Leeuwen,  "Tableau algorithms defined naturally for pictures"  ''Discrete Math.'' , '''157'''  (1996)  pp. 321–362</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. de B. Robinson,  "On the representations of the symmetric group"  ''Amer. J. Math.'' , '''60'''  (1938)  pp. 745–760</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.V. Zelevinsky,  "A generalisation of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence"  ''J. Algebra'' , '''69'''  (1981)  pp. 82–94</TD></TR></table>

Latest revision as of 08:06, 6 June 2020


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=18156
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