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)=5\cdot 3 \cdot 3 \cdot 1\cdot 1 \cdot 1 = 45, \qquad Q(\lambda)=1\cdot 2 \cdot 2 \cdot 3\cdot 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+3\ge 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
    $\begingroup$ Is it true that the array $(h)$ majorates $(q)$, then the inequality would follow from Karamata inequality for the concave function $\log$? $\endgroup$ Jul 7 '16 at 4:40
  • $\begingroup$ @Fёdor: This is a nice idea. While I don't have a counterexample, there is no natural ordering on squares of $\lambda$, so I sort of doubt that. $\endgroup$
    – Igor Pak
    Jul 7 '16 at 5:48
  • 2
    $\begingroup$ It seems to me like the majorization inequality should hold for trees as well (and maybe other classes of posets) but I haven't been able to adapt Fedor's proof. As far as the weaker statement that the moments of the sequence of hooks are greater than the moments of the complementary hooks, that has a simple combinatorial proof for young diagrams and trees alike. $\endgroup$ Jan 8 '17 at 19:10
  • 1
    $\begingroup$ I am fascinated by this phenomenon and I'm glad you figured out he case of trees as well. For a general poset $P$ we can define the hook lengths as the exponents in the denominator of the generating function of its P-partitions, and the contents as the same but for the dual poset. It seems like hooks will majorize contents whenever $P$ is a D-complete poset (and maybe more), and this seems to signal that this story might also have a commutative algebra analog. $\endgroup$ Mar 31 '19 at 18:05
  • 1
    $\begingroup$ One more thing. This is all very mysterious until you notice the similarities of the proof with the incremental proofs of isoperimetric inequalities. Say, you are trying to prove that the square is optimal in $(\mathbb R^2, \ell_\infty)$. What do you do? $\endgroup$
    – Igor Pak
    Mar 31 '19 at 21:43

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_j\in [c_i+j-i,+\infty)$. Summing up these inequalities over all pairs $i<j$ we get the desired inequality $A-B\geqslant 0$.

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

  • $\begingroup$ I am slightly confused by the "array $(h)$ majorates array $(q)$" implication. Is it standard that if the inequality holds for all $\varphi$, then there is an ordering? $\endgroup$
    – Igor Pak
    Jul 8 '16 at 2:19
  • 3
    $\begingroup$ Karamata's inequality (for any convex functions $\varphi$) is known to be a criterion of majorization. Just apply it to the convex functions $\max(x-T,0)$ with all $T$. I think, it must be written explicitly in standard references like Marshall-Olkin. en.m.wikipedia.org/wiki/Karamata%27s_inequality $\endgroup$ Jul 8 '16 at 6:51
  • 3
    $\begingroup$ ++ Another beautiful inequality proof by Fedor! $\endgroup$
    – Suvrit
    Jul 8 '16 at 13:05

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 $\mu\succcurlyeq \nu$ if $$\sum_{i=1}^{r}\mu_i\geq \sum_{i=1}^r \nu_i $$ for all $r\geq 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, $\mu\succcurlyeq \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 $1\le i\le \lambda_j$ and $1\le j\le k$, and edges to be $(i_1,j)\to (i_2,j)$ when $i_2\geq i_1$ and $(i,j_1)\to (i,j_2)$ when $j_2\geq 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:u\to 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 $v\to w$ we have and edge $u\to w$ together with the fact that there is no edge $v\to u$.

    Corollary (1): We have $\mathcal H_{\lambda}\succcurlyeq \mathcal H^{*}_{\lambda}$. Moreover $H(N_0)$ for $N_0=\sum_{1}^k\binom{\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 $u\to v$ we also replace the outgoing edge $v\to w$ by $u\to 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$.


    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Not the answer you're looking for? Browse other questions tagged or ask your own question.