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.

Solution 1:

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$.

Solution 2:

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.

Solution 3:

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.