Prove for all $λ$ contained in $k×l$ box, $w_λ=\sum_{x\in Add(λ)} w(x)-\sum_{y\in Remove(λ)} w(y)=kl-2|λ|$ is positive as long as $n=|λ|<\frac{kl}2$

91 Views Asked by At

I am learning Algebraic Combinatorics from MIT-OCW. Doubt is from the Lecture Notes-$20$,

PDF Link for Notes

In Lemma $190$

For all $\lambda$ contained in a $k\times l$ box, $$w_\lambda=\sum_{x\in Add(\lambda)} w(x)-\sum_{y\in Remove(\lambda)} w(y)=kl-2|\lambda|$$ So this is positive as long as $n=|\lambda|< \frac{kl}2$

To show the unimodality of Gaussian coefficients, the lemma 190 is needed. The note doesn't give explicit reasoning; how can I prove it?

1

There are 1 best solutions below

2
On

Let $\lambda$ be a Young diagram that fits into a $k\times l$ box. Let $\textrm{Add}(\lambda)$ and $\textrm{Remove}(\lambda)$ be the squares one can add to/remove from $\lambda$ to obtain another Young diagram. Let$$w_k(i,j) = (i-j+l)(j-i+k)$$be a function of the squares of the box and let$$w_k(\lambda) = \sum_{x\in \textrm{Add}(\lambda)}w_k(x) - \sum_{y\in \textrm{Remove}(\lambda)}w_k(y).$$

We show $w_k(\lambda) = kl-2|\lambda|$ by induction on $k$. If $k=0$, everything is zero. Now let $\lambda$ fit in a $(k+1)\times l$ box, and let $\lambda'$ be the Young diagram one obtains from $\lambda$ by removing the $m'$ rows of squares that have the same number $j'$ of columns as the $(k+1)$th row. Then $\lambda'$ fits into the upper $k\times l$ subbox and by induction $w_k(\lambda')=kl-2|\lambda'|$.

Now note that the squares in $\textrm{Add}(\lambda')$ and $\textrm{Remove}(\lambda')$ can be almost paired with one another: For every addable square at $(i,j+1)$ to the right of $\lambda'$ there is a removable square at $(i+m_j,j)$, $m_j+1$ being the number of rows in $\lambda'$ of the same width as the $i$th row, and only one addable square at $(M+1,1)$ at the bottom left of $\lambda'$ remains unpaired.

(Note that since $w_k(k+1,1) = w_k(1,l+1) = 0$, the case where $\lambda'$ touches the right or bottom edges of the box doesn't have to be treated specially.)

Since$$(w_{k+1}(i,j+1)-w_{k+1}(i+m_j,j)) - (w_k(i,j+1)-w_k(i+m_j,j)) = -(m_j+1)$$and$$w_{k+1}(M+1,1)-w_k(M+1,1) = M+l,$$it follows that$$w_{k+1}(\lambda')-w_k(\lambda') = M + l + \sum_j -(m_j+1) = l,$$where $j$ ranges over the paired squares.

In terms of addable/removable squares, going from $\lambda'$ to $\lambda$ loses an addable square at $(M+1,1)$ and gains an addable/removable pair at $(M+1,j'+1), (k+1,j')$, so$$\begin{alignat*}{3}w_{k+1}(\lambda)-w_{k+1}(\lambda') &= &&-w_{k+1}(M+1,1) \\&&&+ w_{k+1}(M+1,j'+1) - w_{k+1}(k+1,j') \\ &= &&-2(k+1-M)j' \\ &=&& -2m'j' \\ &=&& -2|\lambda\setminus\lambda'|,\end{alignat*}$$and finally$$\begin{align}w_{k+1}(\lambda) &= w_k(\lambda') + (w_{k+1}(\lambda')-w_k(\lambda')) + (w_{k+1}(\lambda)-w_{k+1}(\lambda')) \\ &= kl-2|\lambda'| + l - 2|\lambda\setminus\lambda'| \\ &= (k+1)l - 2|\lambda|.\end{align}$$