Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $A$ and $B$ be two Young tableaux, i. e. Young diagrams filled with the numbers $1$, $2$, ..., $n$ for some $n$ (not necessarily the same $n$). (They need not be semistandard.)

(a) (Etingof's Lectures on Representation Theory, proof of Lemma 4.40): If $A$ and $B$ share the same Young diagram, then there exist two entries which lie in the same row of $A$ and in the same column of $B$, unless we can make $A$ and $B$ equal by permuting some elements inside their rows in $A$ and permuting some elements inside their columns in $B$.

(b) (Etingof's Lectures on Representation Theory, proof of Lemma 4.41): If the partition corresponding to $A$ is lexicographically larger than that corresponding to $B$ - but both have the same sum -, then there exist two entries which lie in the same row of $A$ and in the same column of $B$.

(c) (Serganova's Representation Notes, lecture 6, Lemma 1.4): If the Young diagram of $B$ has only one less square than $A$ but does not result from $A$ by removing one square, then there exist two entries which lie in the same row of $A$ and in the same column of $B$, or two entries which lie in the same row of $B$ and in the same column of $A$.

I am rather new to Young tableaux, and I haven't looked into Fulton, Stanley or Knuth, but maybe someone can answer on the spot whether there is a more general statement behind these three results?

Oh, and since this fits so nicely: This paper gives a wonderful proof of the Littlewood-Richardson rule, even generalized to the product of a Schur function of a Young diagram with that of a skew Young diagram. Is there a reasonable generalization to the product of two skew Young diagrams?

UPDATE: Claim (c) is wrong, as easily checked for $\lambda = \begin{array}{ccc} 5&1&3\\\\ 2& & \\\\ 4 & & \\\\ \end{array}$ and $\mu = \begin{array}{cc} 1& 2 \\\\ 4 & 3 \end{array}$.

share|improve this question
1  
Please, clarify what you mean by "Young tableau": is it weight $(1,1,\ldots,1)$ (i.e. the entries are $1,2,\ldots,n$)? Also, what is the context for these technical lemmas? –  Victor Protsak Jul 11 '10 at 0:23
    
Good point. Edited my post. The context is representation theory of $S_n$; my main interest in the generalization is the hope that its proof will be less ugly than that for (c) (as usually general results have nicer proofs). –  darij grinberg Jul 11 '10 at 7:44
add comment

2 Answers

up vote 8 down vote accepted

I can't give you your desired "most general" theorem, but I can say a little about this. In (b), the condition "shape(A) is lexicographically larger than shape(B)" is much stronger than it needs to be: "shape(A) is not dominated by shape(B)" will yield the same conclusion (recall the dominance order on partitions: $\lambda$ dominates $\mu$ if $\lambda_1+\cdots+\lambda_i\geqslant\mu_1+\cdots+\mu_i$ for each $i$).

To prove this: suppose all the entries in each row of $A$ are in different columns of $B$. Replace each entry of $B$ with the number of the row in which it appears in $A$; then by assumption the entries in each column of (the modified) $B$ are distinct. So if we sort the entries in this tableau into increasing order, all the entries less than or equal to $i$ will appear in the top $i$ rows. Hence the number of positions in the top $i$ rows of $B$ is at least the number of entries in the top $i$ rows of $A$, i.e. $\lambda_1+\cdots+\lambda_i\geqslant\mu_1+\cdots+\mu_i$ (where $\lambda=\operatorname{shape}(B)$ and $\mu=\operatorname{shape}(A)$).

This is all assuming that $A$ and $B$ have the same size. If $A$ is bigger than $B$, then obviously it goes wrong (because then $\lambda$ can't possibly dominate $\mu$, but the conclusion could easily be false). A more general statement (I think) is the following:

if either ($|\lambda|\geqslant|\mu|$ and $\lambda\ntrianglerighteq\mu$) or ($|\lambda|\leqslant|\mu|$ and $\mu'\ntrianglerighteq\lambda'$) then there are two entries in the same row of $A$ and the same column of $B$.

(Here I'm still writing $\lambda=\operatorname{shape}(B)$ and $\mu=\operatorname{shape}(A)$, $\lambda'$ denotes the conjugate (=transpose) partition to $\lambda$, and $\trianglerighteq$ is the dominance order.)

share|improve this answer
    
Thank you, I didn't know of the dominance order. (It seems, however, that the usual trick for proving (a), (b), (c) won't work here...) –  darij grinberg Jul 13 '10 at 6:54
    
Wait, do you require $\lambda_1+...+\lambda_n=\mu_1+...+\mu_n$? So is this the majorization order? –  darij grinberg Jul 13 '10 at 6:55
    
I've edited in response to your comments; I hope this makes sense. I've heard 'majorization' as a synonym for dominance, but in representation theory everyone says dominance. –  Matt Fayers Jul 13 '10 at 12:52
1  
Okay, it doesn't help with proving (c). But let me remark that your proof also yields (a): Again suppose that any two entries in the same row in $A$ are in different columns in $B$. Then, your argument shows that each column of $B$ has exactly one element in row $1$ of $A$, exactly one element in row $2$ of $A$, ..., exactly one element in row $i$ of $A$, where $i$ is the length of this column (because otherwise, your proof of $\lambda_1+...+\lambda_i\geq \mu_1+...+\mu_i$ could be strengthened to a proof of the strict inequality $\lambda_1+...+\lambda_i > \mu_1+...+\mu_i$ which is absurd). –  darij grinberg Jul 18 '10 at 21:31
1  
So, we can permute the entries within each column of $B$ in such a way that the element that appears in row $1$ of $A$ ends up in row $1$ of $B$, the element that appears in row $2$ of $A$ ends up in row $2$ of $B$, ..., that appears in row $i$ of $A$ ends up in row $i$ of $B$. In other words, every element in the $j$-th row of (my modified tableau) $B$ lies in the $j$-th row of $A$, for every $j$. But this modified tableau $B$ can also be obtained from the tableau $A$ by permuting the entries within each row. So (a) is proven. –  darij grinberg Jul 18 '10 at 21:41
show 2 more comments

Answering your last question, the Littlewood-Richardson rule has indeed been recently extended to skew shapes, see Theorem 6 in this preprint by Lam, Lauve and Sottile

share|improve this answer
    
Thank you. It's not as simple as I hoped judging by the one-skew-and-one-normal-tableau case but it's combinatorial, and I particularly like the application of Hopf algebras. –  darij grinberg Jul 11 '10 at 11:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.