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ⁿ-1)/(q-1) = q^n-1  + q^n-2 + ... +  q² + 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.