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.
 A: Since I am currently writing lecture notes on this topic, let me show how I present the result there, precisely along the lines suggested by Andrew Wilson. This is a slight variation of one the proofs in Macdonald, Symmetric functions and Hall polynomials. I think it is both conceptually and computationally  simple.
Lemma:
The inequality $\lambda\geq\mu$ holds if and only if the Young diagram from $\lambda$ can be obtained from that of $\mu$ by successively moving boxes from a lower to a higher row (one box at a time), in such a way that each intermediate step is the Young diagram of a partition. 
Note that this Lemma immediately implies the duality: simply apply the corresponding moves in the opposite order to the conjugate partitions.
Proof:
Moving a box from row $j$ to row $i$ in $\mu$ (where $i<j$) gives 
$$(\nu_1,\dots,\nu_m)=(\mu_1,\dots,\mu_{i-1},\mu_i+1,\dotsm,\mu_j-1,\dots,\mu_m).$$
If the result is a partition, it is clear that $\nu>\mu$. This proves the if statement. 
For  the only if statement, it suffices to prove that, if $\lambda>\mu$, then there exists such a partition  $\nu$ 
with $\nu\leq\lambda$. Iterating this procedure, we must eventually 
reach a step when $\nu=\lambda$. 
The inequality $\nu\leq\lambda$ is equivalent to
$$\lambda_1+\dots+\lambda_k>\mu_1+\dots+\mu_k,\qquad i\leq k\leq j-1.\qquad(*)$$
Thus, it is natural to define $i$ as the smallest integer $k$ such that ($*$) holds and 
$j$ as the smallest integer $k$ such that $k>i$ and ($*$) fails.
Note that $i$ exists by our assumption $\lambda>\mu$, and $j$ exists since $\lambda$ and $\mu$ are partitions of the same number. 
It remains to prove that, with these values of $i$ and $j$, $\nu$ is a partition.
That is, we must prove that $\mu_{i-1}>\mu_i$ (or $i=1$) and  $\mu_j>\mu_{j+1}$.
Note that $i$ is  the smallest integer such that $\lambda_i>\mu_i$. 
It follows that
$\mu_{i-1}=\lambda_{i-1}\geq\lambda_i>\mu_i$ (or $i=1$). 
Moreover, since $\lambda_1+\dots+\lambda_{j-1}>\mu_1+\dots+\mu_{j-1}$ and $\lambda_1+\dots+\lambda_{j}=\mu_1+\dots+\mu_{j}$ 
and  $\lambda_1+\dots+\lambda_{j+1}\geq\mu_1+\dots+\mu_{j+1}$ we must have $\lambda_j<\mu_j$ and $\lambda_{j+1}\geq\mu_{j+1}$. Combining these facts gives
$\mu_{j+1}\leq\lambda_{j+1}\leq\lambda_j<\mu_j$. 
A: 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.
A: 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 chosen for $l$ respectively $k$ are not always the unique ones that will make the argument work, just the minimal respectively maximal ones.
A: This question is pretty old, but I would like to propose "a nice clever and concise/intuitive proof" as asked, although it may be considered not formal enough. It is a variant of the answer by Hjalmar Rosengren.
In his 1973 paper, Brylawski shows that all partitions of integer $n$ and the dominance order are obtained from the initial partition $(n)$ by iterating the following two rules on any partition (assuming that the last part is followed by a null part):

*

*if its $i$-th part is strictly larger than its $i+1$-th one, then decrease the $i$-th part by $1$ and increase the $i+1$-th one by $1$;

*if its $i$-th part is equal to its $i+1$-th part plus $1$, and its $i+1$-th part is equal to its $j$-th part plus $1$, then decrease the $i$-th part by $1$ and increase the $j$-th one by $1$.

This may be represented graphically on Ferrers diagrams as follows:
                                
In the case $n=7$, for instance, we obtain:
                            
Then, just notice that applying the first Brylawski rule to a partition is equivalent to applying the second rule to its conjugate; and conversely, applying the second Brylawski rule to a partition is equivalent to applying the first rule to its conjugate.
From this, the equivalence in the asked question is obvious: a partition $\lambda$ is reachable from a partition $\tau$ by iterating the Brylawski rules if and only if the conjugate $\tau'$ is reachable from the conjugate $\lambda'$ by iterating these rules.
Several studies envision the lattice of integer partitions from this iterated rules point-of-view, see for instance this one.
A: 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}$
A: I would be curious to know, if this would be an acceptable proof. I find no flaw, but then I am not an expert in this area:
Let $\lambda,\tau$ be two partitions of $n$. To avoid notational clutter extend them to infinite sequences by adding zeros, so that I may now add up to infinity but the sums will always be finite. Then $\lambda \leq \tau$ is defined by
$$ (1) \quad \quad \forall i\in \mathbb{N} : \quad \sum_{j=1}^i \lambda_j \leq \sum_{j=1}^i \tau_j. $$
We will show first that $\lambda \leq \tau$ implies $\tau'\leq \lambda'$. The desired order relation $\tau'\leq \lambda'$ is equivalent to 
$$ (2) \quad \forall k\in \mathbb{N} : \quad \sum_{j=k}^\infty \lambda^\prime_j \leq \sum_{j=k}^\infty \tau^\prime_j, $$
because for both sequences $\sum_{j=k}^\infty \lambda^\prime_j = n - \sum_{j=1}^{k-1} \lambda^\prime_j$ for $k=1,2,\ldots$.
To deduce (2) from (1), note that (2) for the value $k=1$ holds, because by assumption
$$ \sum_{j=1}^\infty \lambda^\prime_j = \sum_{j\in \mathbb{N}} \lambda_j \leq \sum_{j\in \mathbb{N}}  \tau_j = \sum_{j=1}^\infty \tau^\prime_j. $$
For the case $k=2$ note that the sequence $(\lambda_2', \lambda_3', ...)$ is the conjugate of the sequence $(\hat{\lambda}_j):=(\max [ \lambda_j-1,0])$. Now for the new sequences $\hat{\lambda},\hat{\tau}$ thus defined, we have 
$$ (1^\prime) \quad \quad \forall i\in \mathbb{N} : \quad \sum_{j=1}^i \hat{\lambda_j} \leq \sum_{j=1}^i \hat{\tau_j}, $$
because if for some $i$ we have $\hat{\lambda}_i=0$, there is no problem, if the statement was true for $i-1$ and if $\hat{\lambda}_i>0$, then
$$ \quad \sum_{j=1}^i \hat{\lambda_j} =  -i + \sum_{j=1}^i \lambda_j \leq -i + \sum_{j=1}^i \tau_j \leq \sum_{j=1}^i \hat{\tau_j}. $$
The claim for $k=2$ now follows by applying the previous argument for the case $k=1$ to the new sequences with the hats and the overall claim for all $k$ follows by iterating this argument. The other direction follows by symmetry as the conjugate of the conjugate is the original sequence. Q.E.D.
Note that the sequences $(\hat{\lambda}_j), (\hat{\tau}_j)$ need not be partitions of the same integer any more. But the argument for $k=1$ already avoids that the total sum is actually the same. So this proof shows that (1) implies (2) even if the two partitions belong to two different integers. To get the equivalence of $\lambda \leq \tau$ and $\tau^\prime \leq \lambda^\prime$ using this argument, we have to use  that they partition the same integer as this is used in the equivalence of (2) and the order of the conjugates.
