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

2 AnswersI 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)$

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

2 Asked on November 3, 2021

1 Asked on November 3, 2021 by alex-gavrilov

0 Asked on November 3, 2021 by mohammad-golshani

2 Asked on November 3, 2021 by bryanjaeho

1 Asked on November 3, 2021 by diverietti

ag algebraic geometry complex geometry cv complex variables homogeneous spaces symmetric spaces

2 Asked on November 3, 2021 by bananeen

ag algebraic geometry analytic geometry complex geometry cv complex variables

1 Asked on November 3, 2021

0 Asked on November 3, 2021 by guy-crouchback

0 Asked on November 3, 2021 by mikhail-bondarko

ag algebraic geometry birational geometry chow groups motives reference request

7 Asked on November 3, 2021

at algebraic topology gn general topology graph theory gt geometric topology reference request

1 Asked on November 3, 2021

1 Asked on November 3, 2021 by jecl

algebraic number theory analytic number theory nt number theory

2 Asked on November 3, 2021

1 Asked on November 3, 2021

co combinatorics homological algebra rt representation theory

2 Asked on November 3, 2021

ag algebraic geometry at algebraic topology complex geometry reference request

2 Asked on November 3, 2021 by rohil-prasad

dg differential geometry differential topology gt geometric topology mg metric geometry

2 Asked on November 3, 2021

mp mathematical physics pr probability quantum field theory schwartz distributions

3 Asked on November 3, 2021

higher category theory morita equivalence morita theory noncommutative algebra noncommutative rings

1 Asked on November 3, 2021 by rajesh-d

Get help from others!

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

Recent Answers

- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- eric_kernfeld on How to test consistency of responses?
- kjetil b halvorsen on How to test consistency of responses?
- Philipp on How do i draw a ray in unity
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed

© 2022 AnswerBun.com. All rights reserved.