# Proof of the duality of the dominance order on partitions

Could anyone provide me with a nice proof that the dominance order $\leq$ on partitions of an integer $n$ satisfies the following: if $\lambda, \tau$ are 2 partitions of $n$, then $\lambda \leq \tau \Longleftrightarrow \tau ' \leq \lambda '$, where $\lambda'$ is the conjugate partition of $\lambda$ (i.e. the transpose of the set of 'dots' which $\lambda$ represents).

I feel like there must be a nice clever and concise/intuitive proof of this, but all I can come up with is an ugly brute force approach based on the definition of sums of the components $\lambda_i$. Could anyone suggest a particularly nice way to obtain this result? Many thanks.

• In fact I seem to have now found a proof of quite the opposite result - that conjugation preserves the order - in MacDonald's Symmetric Functions and Hall Polynomials, (1.11). The proof seems valid to me, but I've been asked to prove that conjugation reverses the order, is this incorrect? – Tom Feb 13 '12 at 1:05
• Conjugation definitely reverses the ordering; preserving the ordering would be absurd given that the maximal partition $(n)$ and the minimal paritition $(1,1,\ldots,1)$ are conjugates of each other. You must have misread Macdonald (who has only one capital in his name; no relation to hamburgers). – Marc van Leeuwen Feb 13 '12 at 10:20

This is one of the most fundamental properties of the dominance ordering; one should not be surprised or ashamed at actually using the definition of that ordering in proving it. However, here is an approach that you may find less technical, as it shows the equivalence of the definition of the dominance ordering with a characterisation that makes the anti-symmetry obvious.

I will denote the Young diagram of a partition $\lambda$ by $[\lambda]$, considered as a subset of the quarter-lattice $\mathbf N_{>0}^2$, of which I will also consider the following subsets: the "upper half planes" $H_k=\{(i,j)\in\mathbf N_{>0}^2\mid i\leq k\}$ for $k\in\mathbf N$, and the "upper right diagonal half planes" $D_l=\{(i,j)\in\mathbf N_{>0}^2\mid i-j\leq l\}$ for $l\in\mathbf Z$. (One should take the "half plane" with a grain of salt: that is what the subsets of $\mathbf R^2$ defined by the same inequalities look like; in particular note that $H_0=\emptyset$.) One can now give the definition of the dominance order as follows.

Definition. For two partitions $\lambda,\mu$ of the same number $n\in\mathbf N$, one has $\lambda\leq\mu$ if and only if for all $k\in\mathbf N$ one has $|[\lambda]\cap H_k|\leq|[\mu]\cap H_k|$.

Lemma. For two partitions $\lambda,\mu$ of the same number $n\in\mathbf N$, the condition $\lambda\leq\mu$ holds if and only if for all $l\in\mathbf Z$ one has $|[\lambda]\cap D_l|\leq|[\mu]\cap D_l|$.

Admitting this lemma for now, one easily deduces the anti-symmetry of conjugation: \begin{align} \lambda\leq\mu &\iff \forall l\in\mathbb Z:|[\lambda]\cap D_l|\leq|[\mu]\cap D_l| \\& \iff \forall l\in\mathbb Z:|[\lambda']\cap D_{-1-l}|\geq|[\mu']\cap D_{-1-l}| \\& \iff \lambda' \geq \mu', \\\end{align} where the middle equivalence comes from the fact that $D_{-1-l}$ is the "transpose" of the complement in $\mathbf N_{>0}^2$ of the set $D_l$, so that the partial diagrams have been replaced by their transpose complements, and since $|[\lambda]|=n=|[\mu]|$ this changes their size from $s$ to $n-s$. Note that only here do we use $|[\lambda]|=|[\mu]|$, the lemma would be valid for partitions of different sizes (but the partial orders in that setting are nevertheless of no significance).

Proof of the lemma. We prove by contraposition: there exists some $k\in\mathbf N$ with $|[\lambda]\cap H_k|>|[\mu]\cap H_k|$ if and only if there exists some $l\in\mathbf Z$ such that $|[\lambda]\cap D_l|>|[\mu]\cap D_l|$. While the details below may seem a bit technical, the idea is simple: in the first part we pass from $k$ to $l$ using $\mu$ only, pushing $D_l$ as far to the right as possible while keeping the "octant" $H_k\setminus D_l$ inside the diagram $[\mu]$, and in the second part we pass from $l$ to $k$ using $\lambda$ only, by similarly pushing $H_k$ down as far as possible while keeping the same octant inside the diagram $[\lambda]$.

Suppose first the existence of such $k\in\mathbf N$ with $|[\lambda]\cap H_k|>|[\mu]\cap H_k|$. Let $(k,y)$ be the first square of row $k$ that is absent from $[\mu]$ (so in fact $y=\mu_k+1$), and put $l=k-y$. Then $[\mu]\cap D_l\subseteq [\mu]\cap H_k$ (since any squares $(i,j)$ of $D_l\setminus H_k$ have $i>k$ and $j\geq i-l>y$ and therefore $(i,j)\notin[\mu]$) while $H_k\setminus D_l\subseteq[\mu]$ (the "maximal" square $(k,y-1)$ of $H_k\setminus D_l$, if it exists, lies in $[\mu]$ by construction). One thus has $|[\mu]\cap D_l|=|[\mu]\cap H_k|-|H_k\setminus D_l|$, and this suffices to obtain the required inequality: $$|[\lambda]\cap D_l|\geq|[\lambda]\cap H_k|-|H_k\setminus D_l| >|[\mu]\cap H_k|-|H_k\setminus D_l|=|[\mu]\cap D_l|.$$ Conversely suppose the existence of $l\in\mathbf Z$ such that $|[\lambda]\cap D_l|>|[\mu]\cap D_l|$. Let $k\geq\max(0,l+1)$ be minimal such that $(k+1,k-l)\notin[\lambda]$. By the choice of $k$ we have $[\lambda]\cap D_l\subseteq [\lambda]\cap H_k$ (the minimal square $(k+1,k-l+1$ of $D_l\setminus H_k$ does not lie in $[\lambda]$), and $H_k\setminus D_l\subseteq[\lambda]$ (the maximal square $(k,k-l-1)$ of $H_k\setminus D_l$, if it exists, lies in $[\lambda])$. Then by a similar argument as above, $$|[\lambda]\cap H_k| = |[\lambda]\cap D_l|+|H_k\setminus D_l| >|[\mu]\cap D_l|+|H_k\setminus D_l| \geq |[\mu]\cap H_l|.$$

It should be noted that the values values chosen for $l$ respectively $k$ are not always the unique ones that will make the argument work, just the minimal respectively maximal ones.

• A wonderful proof, thank you! Very thoroughly explained, I'm very grateful. Incidentally, regarding my above comment everyone was quite right, my apologies but I somehow managed to foolishly misread Macdonald, despite double-checking to make sure I had read it right initially - such are the perils of doing maths on no sleep... – Tom Feb 13 '12 at 19:54

It seems to me that what you're being asked to prove is correct. (Maybe MacDonald is discussing a different order? I'm not sure, I don't have the text here.)

The only proof sketch (emphasis on sketch) I can give that seems more intuitive is to think of how dominance order affects the Ferrers diagram. Given a partition $\tau$, we can make a partition $\lambda$ such that $\lambda \leq \tau$ by "moving dots" up and to the left in the diagram (assuming French notation). After conjugation, this movement would now be down and to the right, implying $\tau^{\prime} \leq \lambda^{\prime}$. Obviously, this is far from rigorous, but you might be able to write it out a bit more formally without things getting too ugly.

I just stumbled across this question. This is, I think, a somewhat more elementary proof.

Proof by induction on number of elements:

Step 1: Clearly is true for 1.

Step 2: Assume true for partitions of size $k < l$.

Let $A= \lbrace a_1,a_2,...\rbrace$ and $B=\lbrace b_1, b_2, ... \rbrace$ be partitions of l so that $B \unrhd A$. Then:

$$\sum_{h=1}^k a_h \leq \sum_{h=1}^k b_h \space \forall k$$

Let the largest part of $A$ be size $n$ and assume there are $i$ copies, and let the largest part of $B$ be size $m$ and assume there are $j$ copies. Then it must be that $m \geq n$. Also, if $i > j$ then $m j + b_{j+1} \geq n (j + 1)$, and since $b_{j+1} < m$, it must be that $m (j+1) > n (j + 1)$, hence $m > n$.

Construct new partitions $A'$ and $B'$ of $l-1$ by replacing one of the $n$ parts in A with $n-1$ and one of the m parts in B with m-1.

Then $B' \unrhd A'$.

Proof:

We want to show: $$\begin{eqnarray}\sum_{h=1}^k a_h - \small\begin{cases} 0 \text{ if } k < i \\ 1 \text{ if } k \geq i \end{cases} \space \large\leq \space \normalsize\sum_{h=1}^k b_h - \small\begin{cases} 0 \text{ if } k < j \\ 1 \text{ if } k \geq j \end{cases} \end{eqnarray} \space \forall k$$ Look at the sum of the first $k$ terms for any $k$. There are a number of cases:

Case 1: $j \geq i$:

• If $k < i$ the sums are unchanged from $B$ and $A$, so the RHS is $\geq$.
• If $k \geq i$ and $k < j$, the LHS sum has been decreased by $1$, so the RHS sum is $>$.
• If $k \geq j$, both the $A$ and $B$ sums have been decreased by $1$, so the RHS sum is $\geq$.

Case 2: $i > j$:

Note that we must have $m > n$.

• If $k \geq j$, both the $A$ and $B$ sums have been decreased by $1$, so the RHS sum is $\geq$.
• If $k < j$, the equation reduces to $k n \leq k m$, so the RHS is $\geq$.
• If $k \geq j$ and $k < i$, things depend on how $b_k$ compares to $n$:
• If $b_k \geq n$, then each of the RHS terms is $\geq$ the LHS terms, so the RHS is $\geq$.
• If $b_k < n$, it still must be true that: $$n (k+1) \leq \sum_{h=1}^{k+1} b_h \space \implies n k < \sum_{h=1}^{k} b_h \implies n k \leq \sum_{h=1}^{k} b_h - 1$$ So, again, the RHS is $\geq$.

Now, Let $\hat{B}'$ be the conjugate of $B'$ and $\hat{A}'$ be the conjugate of $A'$. By induction, $\hat{A}'$ dominates $\hat{B}'$.

Let $\hat{B}$ be the conjugate of $B$ and $\hat{A}$ the conjugate of $A$. Then:

• $\hat{B}$ is obtained from $\hat{B}'$ by adding 1 to the m'th part (or, by adding a $1$ part if there isn't an m'th part).
• $\hat{A}$ is obtained from $\hat{A}'$ by adding 1 to the n'th part (or, by adding a $1$ part if there isn't an n'th parht).

Since $m \geq n$, adding $1$ to each partition in this way preserves the dominance order and $\hat{A} \unrhd\hat{B}$