# What is the most general "two in one row for A & in one column for B" theorem?

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}$.

• 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? Commented Jul 11, 2010 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). Commented Jul 11, 2010 at 7:44

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.)

• 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...) Commented Jul 13, 2010 at 6:54
• Wait, do you require $\lambda_1+...+\lambda_n=\mu_1+...+\mu_n$? So is this the majorization order? Commented Jul 13, 2010 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. Commented Jul 13, 2010 at 12:52
• 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). Commented Jul 18, 2010 at 21:31
• 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. Commented Jul 18, 2010 at 21:41

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

• 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. Commented Jul 11, 2010 at 11:58