Inequality for hook numbers in Young diagrams

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.

MathOverflow Asked by Igor Pak on January 5, 2022

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
• if $$j_1=j_2$$ and $$i_1
• if $$j_1=j_2, i_1=i_3$$ and $$i_2
• 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

Related Questions

Examples of $aleph_0$-categorical nonhomogeneous structures

2  Asked on November 3, 2021

Extending a holomorphic vector bundle: a reference request

1  Asked on November 3, 2021 by alex-gavrilov

Closed walks on an $n$-cube and alternating permutations

2  Asked on November 3, 2021 by bryanjaeho

Bounded non-symmetric domains covering a compact manifold

1  Asked on November 3, 2021 by diverietti

Residues in several complex variables

2  Asked on November 3, 2021 by bananeen

What kinds of papers does the Indiana University Mathematics Journal publish?

1  Asked on November 3, 2021

Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable?

0  Asked on November 3, 2021 by guy-crouchback

Which field extensions do not affect Chow groups?

0  Asked on November 3, 2021 by mikhail-bondarko

Reference for topological graph theory (research / problem-oriented)

7  Asked on November 3, 2021

Is a direct sum of flabby sheaves flabby?

1  Asked on November 3, 2021

Algebraicity of a ratio of values of the Gamma function

1  Asked on November 3, 2021 by jecl

Classification of subgroups of finitely generated abelian groups

2  Asked on November 3, 2021

An enumeration problem for Dyck paths from homological algebra

1  Asked on November 3, 2021

Circular track riddle

1  Asked on November 3, 2021

Fundamental group of a compact branched cover

2  Asked on November 3, 2021

How do you know that you have succeeded-Constructive Quantum Field Theory and Lagrangian

2  Asked on November 3, 2021

Does Morita theory hint higher modules for noncommutative ring?

3  Asked on November 3, 2021

Bounding the smallest eigenvalue of a matrix generated by a positive definite function

1  Asked on November 3, 2021 by rajesh-d