# 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? –  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

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

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. –  darij grinberg Jul 11 '10 at 11:58