First Homework
Math 662, Young Tableaux
28 September, 2004

1. Prove that conjugation of Young diagrams induces an anti-automorphism for the dominance partial order on partitions.

   
   

2. Let $\Box_{k,l}$ be the partition $(l^k)$ of box shape with $k$ rows and $l$ columns. Adapt the first proof of the identity
   $$\sum_{\lambda\subset\Box_{k,l}} 1\ =\ \binom{k+l}{k;l}\,,$$
   to prove the corresponding weighted version
   $$\sum_{\lambda\subset\Box_{k,l}} q^{\vert\lambda\vert}\ =\ \binom{k+l}{k;l}_q\,,$$
   where $\binom{k+l}{k;l}_q$ is the $q$-binomial coefficient of Gauß. (Replace each integer $n$ in the definition of the ordinary binomial coefficient by the $q$-integer $(q^n-1)/(q-1)=q^{n-1}+q^{n-2}+\dotsb+q^2+q+1$.)

   
   

3. Prove that the following operations on tableaux commute with standardization
   1. Schützenberger's jeu de taquin
   2. Schensted insertion.

4. Formulate and prove a precise statement concerning the reversibility of Schensted insertion.

   
   

5. Following the proofs in the course about longest disjoint increasing subsequences, formulate and prove a result about longest disjoint decreasing subsequences, and the relation between increasing and decreasing subsequences.

   
   

6. Show that column insertion preserves Knuth equivalence of words.

   
   

7. Prove or disprove: The `switching' defined in the combinatorial proof that Schur functions are symmetric defines an action of the infinite symmetric group on tableaux.