Inequality for hook numbers in Young diagrams

MathOverflow Asked by Igor Pak on January 5, 2022

Consider a Young diagram $lambda = (lambda_1,ldots,lambda_ell)$. For a square $(i,j) in lambda$, define hook numbers $h_{ij} = lambda_i + lambda_j’ -i – j +1$ and complementary hook numbers $q_{ij} = i + j -1$. Let
$$H(lambda) = prod_{(i,j) in lambda} h_{ij} ,, qquad
Q(lambda) = prod_{(i,j) in lambda} q_{ij},.

Question: Is there an elementary proof of the following inequality:
$$H(lambda) le Q(lambda),

where the inequality becomes the equality only for rectangular shapes.

For example, when $lambda = (3,2,1)$ we have
$$H(lambda)=5cdot 3 cdot 3 cdot 1cdot 1 cdot 1 = 45, qquad
Q(lambda)=1cdot 2 cdot 2 cdot 3cdot 3 cdot 3 = 108.

Let me mention that
$$sum_{(i,j) in lambda} h_{ij} = sum_{(i,j) in lambda} q_{ij},

so somehow this says that $q_{ij}$ are more evenly distributed than $h_{ij}$.

Note: this inequality is a corollary of the results in our recent paper. The proof of the main result is algebraic and quite involved.

P.S. Originally posted on MSE since I thought this might be an easy exercise. Now I don’t.

UPDATE (July 8, 2015): Petrov’s elegant proof gives a stronger result. In particular, it proves what I suggested above, that the variance of complementary hooks $(q_{ij})$ is smaller than that of the usual hooks $(h_{ij})$. To see this, take $varphi = x^2$ and use $Var(X) = E[X^2] – E[X]^2$.

Note also, as explained in the comments, the proof shows the hook numbers majorize the complementary hooks, when both are ordered from largest to smallest. For the example above: $5 ge 3,$ $5+3ge 3+3$, etc. This is quite remarkable and perhaps even counterintuitive.

SECOND UPDATE: We just wrote a paper on the subject with a different proof.

2 Answers

I was recently thinking about this question again and I came up with another way to explain the result $$mathcal H_{lambda}=left{ h(i,j)right}_{(i,j)in lambda}succcurlyeq left{ h^{*}(i,j)right}_{(i,j)in lambda}=mathcal H^{*}_{lambda} tag{1}$$ in a way that (i) combinatorially describes the sequence of Robin Hood moves to get from $mathcal H_{lambda}$ to $mathcal H^{*}_{lambda}$ and (ii) gives bijective proofs of the various inequalities that follow. In particular there is a bijective explanation for the original inequality: $$prod_{(i,j)in lambda} h(i,j)le prod_{(i,j)in lambda} h^{*}(i,j) tag{2}$$

Majorization and RH moves: Suppose that $mu, nu$ are two integer partitions of $n$. We say that $musucccurlyeq nu$ if $$sum_{i=1}^{r}mu_igeq sum_{i=1}^r nu_i $$ for all $rgeq 1$ (if the partitions do not have the same number of parts, we can add extra zero entries at the end).

A Robin Hood (RH) move on $mu$ is to pick to parts $mu_i> mu_j$ and replace them with $mu_i -1, mu_j+1$ and reorder the terms. This can be pictured on the associated Young diagram as the move which removes a single square at the end of a row and attaches it at the end of some row of shorter length while preserving the property of being a partition. These and their inverse also more frequently known as lowering/raising operators, I just like the metaphor of giving to the less fortunate parts of the partition.

A fundamental fact is that RH moves describe the covering relation in the majorization poset of partitions. In other words, $musucccurlyeq nu$ is equivalent to being able to obtain $nu$ from $mu$ by successively applying RH moves. When working with majorization in combinatorial settings this description is often more desirable than the analytic description (such as when working with symmetric functions, like in Macdonald's book, for example).

Partitions as directed graphs: Given a partition $lambda=(lambda_1,dots,lambda_k)$, its Young diagram can also be viewed as a directed graph $G(lambda)$ by taking the vertices to be the lattice points $(i,j)$ with $1le ile lambda_j$ and $1le jle k$, and edges to be $(i_1,j)to (i_2,j)$ when $i_2geq i_1$ and $(i,j_1)to (i,j_2)$ when $j_2geq j_1$. Notice that equality is allowed, so there is a self loop at every vertex. The graph $G^{*}(lambda)$ is defined the same as $G(lambda)$ but with all the edges reversed.

The set of outdegrees of $G(lambda)$ is precisely $mathcal H(lambda)$ and similarly the outdegrees of $G^{*}(lambda)$ for the set $mathcal H^{*}(lambda)$. We will think of the multisets $mathcal H(lambda),mathcal H^{*}(lambda)$ as partitions of $|lambda|+N$ where $$N= sum_{i=1}^{k}binom{lambda_i}{2}+sum_{i=1}^{r}binom{lambda'_i}{2}.$$ Here $lambda'$ is the conjugate partition of $lambda$.

We can put a total order on the edges of $G(lambda)$ that aren't loops by making all horizontal edges come before vertical edges and the edge $(i_1,j_1)to (i_2,j_1)$ comes before $(i_3,j_2)to (i_4,j_2)$

  • if $j_1<j_2$
  • if $j_1=j_2$ and $i_1<i_3$
  • if $j_1=j_2, i_1=i_3$ and $i_2<i_4$
  • with a similar order on the vertical edges. Therefore we can refer to the nonloop-edges in order as ${e_1,e_2,dots,e_N}$.

    We can define the sequence of directed graphs ${G(t)}_{t=1}^{N}$ by $G(1)=G(lambda)$ and obtaining $G(k+1)$ from $G(k)$ by reversing the direction of edge $e_k$. The final graph is $G(N)=G^{*}(lambda)$. Let $H(t)$ denote the partition of $|lambda|+N$ given by the outdegrees of $G(t)$.

    Theorem: The partition $H(t+1)$ is obtained from $H(t)$ by an RH move.

    Proof: $H(t+1)$ differs from $H(t)$ simply by the reversal of edge $e_t:uto v$. We see that the parts $(deg(u),deg(v))$ get sent to $(deg(u)-1,deg(v)+1)$. So we simply have to check that $deg(u)>deg(v)$ in $G(t)$, but this follows by checking that for every edge $vto w$ we have and edge $uto w$ together with the fact that there is no edge $vto u$.

    Corollary (1): We have $mathcal H_{lambda}succcurlyeq mathcal H^{*}_{lambda}$. Moreover $H(N_0)$ for $N_0=sum_{1}^kbinom{lambda_i}{2}$ recovers the multiset of semi-hooks from the Pak-Petrov-Sokolov paper, and we have $$H(0)succcurlyeq H(N_0)succcurlyeq H(N).$$

    Bijective proof of (2): The quantity $prod_{(i,j)in lambda} h(i,j)$ counts the number of subgraphs of $G(lambda)$ of outdegree 1 at every vertex.The inequality follows if we can describe an injection from the set of such subgraphs to the subgraphs of outdegree 1 of $G^{*}(lambda)$.

    Start with a subgraph of outdegree 1 of $G(1)$ and start reversing the edges one by one according to the order defined previously producing an outdegree 1 subgraph of $G(t)$ for every $t$. When we reverse the edge $uto v$ we also replace the outgoing edge $vto w$ by $uto z$ where $z$ is such that $v+z=u+w$ as vectors (in other words, $z,w,v,u$ are the vertices of a (possibly degenerate) rectangle). This ensures that the subgraph remains of outdegree 1.

    Notice that this is an injection because it can be performed backwards in a unique way whenever it is possible. When the partition is not a rectangle and we try to run the process backwards, the solution to $v+z=u+w$ may take us to a square outside of $lambda$ so we conclude that our map will be a strict injection in that case.

    Note: The injection defined above may seem a bit arbitrary but it is simply combining the RH moves with the bijective proof of $$(a-1)(b+1)geq ab$$ for some integers $a>b$.

    Answered by Gjergji Zaimi on January 5, 2022

    Not sure, please check carefully. (Well, now more sure and the argument is more direct.)

    I claim that the array $(h)$ majorates the array $(q)$, that is, $sum varphi (h_{ij})geqslant sum varphi(q_{ij})$ for any convex function $varphi$, in particular for $-log$, that is your inequality.

    Denote the hook lengths of the first (largest) column by $0<c_1<c_2<dots<c_m$. Then the hooks in $i$-th row, which contains $c_i-i+1$ squares, are all numbers from 1 to $c_i$ except $c_i-c_1$, $c_i-c_2$, $dots$, $c_i-c_{i-1}$ (this elementary claim is well-known, it shows the equivalence of Frobenius and the hook length formulae.) That is, $$ A:=sum varphi(h_{ij})=sum_i bigl(varphi(1)+ldots+varphi(c_i)bigr)-sum_{i<j} varphi(c_j-c_i). $$ Clearly $$ B:=sum varphi(q_{ij})=sum_i bigl(varphi(m-i+1)+ldots+varphi(c_i+m-2i+1)bigr). $$

    For $i<j$, we have: $$ varphi(j-i)+varphi(c_j-i+1)geqslant varphi(c_j-c_i)+varphi(c_i+j-2i+1), $$ since for $c_j=c_i+j-i$ the equality takes place, and the difference of two sides increases as a function of $c_jin [c_i+j-i,+infty)$. Summing up these inequalities over all pairs $i<j$ we get the desired inequality $A-Bgeqslant 0$.

    If $varphi$ is strictly convex, then all inequalities are sharp only for a rectangle.

    Answered by Fedor Petrov on January 5, 2022

    Add your own answers!

    Ask a Question

    Get help from others!

    © 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP