# The Unapologetic Mathematician

## The Dominance Order on Partitions

Now we want to introduce a partial order on the collection of partitions called the “dominance order”. Given partitions $\lambda=(\lambda_1,\dots,\lambda_k)$ and $\mu=(\mu_1,\dots,\mu_l)$, we say that $\lambda$ “dominates” $\mu$ — and we write $\lambda\trianglerighteq\mu$ — if

$\displaystyle\lambda_1+\lambda_2+\dots+\lambda_i\geq\mu_1+\mu_2+\dots+\mu_i$

for all $i\geq1$.

We can interpret this by looking at their Ferrers diagrams. First look at the first rows of the diagrams. Are there more dots in the diagram for $\lambda$ than in that for $\mu$? If so, so far so good; move on to the second row. Now are there more dots in the first two rows for $\lambda$ than there are in the first two rows for $\mu$? If so, keep going. If ever there are more dots above the $i$th row in the Ferrers diagram of $\mu$ than there are in the Ferrers diagram for $\lambda$, then the condition fails. If ever we run out of rows in one diagram, we just say that any lower rows we need have length zero.

Let’s consider two partitions of $6$: $\lambda=(4,2)$ and $\mu=(3,2,1)$. They have the following Ferrers diagrams:

$\displaystyle\begin{array}{cccc}\bullet&\bullet&\bullet&\bullet\\\bullet&\bullet&&\end{array}\qquad\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\\\bullet&&\end{array}$

In the first rows, $\lambda$ has four dots while $\mu$ has three, and $4\geq3$. Moving on, $\lambda$ has six dots in the first two rows while $\mu$ has five, and $6\geq5$. Finally, $\lambda$ has six dots (still!) in the first three rows while $\mu$ also has six, and $6\geq6$. Since the inequality holds for all positive $i$, we find that $\lambda$ dominates $\mu$.

As another example, let $\lambda=(3,3)$ and $\mu=(4,1,1)$:

$\displaystyle\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet\end{array}\qquad\begin{array}{cccc}\bullet&\bullet&\bullet&\bullet\\\bullet&&&\\\bullet&&&\end{array}$

This time, the first rows have three and four dots, respectively — $\lambda_1\leq\mu_1$. We’re on our way to showing that $\lambda\trianglelefteq\mu$. But the first two rows have six dots and five dots, respectively — $\lambda_1+\lambda_2\geq\mu_1+\mu_2$. Since the inequality has flipped sides, neither one of these partitions can dominate the other. Dominance is evidently only a partial order, not a total order.

We can put all the partitions of $n$ into a structure called a “Hasse diagram”, which tells us at a glance which partitions dominate which. This is a graph with partitions at the verices. We draw an arrow from $\mu$ to $\lambda$ if $\lambda\trianglerighteq\mu$. For partitions of $6$, this looks like

$\displaystyle\begin{array}{ccccc}&&(6)&&\\&&\uparrow&&\\&&(5,1)&&\\&&\uparrow&&\\&&(4,2)&&\\&\nearrow&&\nwarrow&\\(3,3)&&&&(4,1,1)\\&\nwarrow&&\nearrow&\\&&(3,2,1)&&\\&\nearrow&&\nwarrow&\\(3,1,1,1)&&&&(2,2,2)\\&\nwarrow&&\nearrow&\\&&(2,2,1,1)&&\\&&\uparrow&&\\&&(2,1,1,1,1)&&\\&&\uparrow&&\\&&(1,1,1,1,1,1)&&\end{array}$

December 17, 2010