# 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 -

1. […] We will have use of the following technical result about the dominance order: […]

Pingback by The Dominance Lemma « The Unapologetic Mathematician | December 20, 2010 | Reply

2. […] biggest problem with the dominance order is that it’s only a partial order. That is, there are some pairs of partitions and so that […]

Pingback by The Lexicographic Order on Partitions « The Unapologetic Mathematician | December 21, 2010 | Reply

3. […] where and . If — where is the group algebra element we’ve defined — then dominates […]

Pingback by Corollaries of the Sign Lemma « The Unapologetic Mathematician | December 31, 2010 | Reply

4. […] can, however, extend the idea of the dominance order to general compositions. As usual we say that […]

Pingback by Compositions « The Unapologetic Mathematician | January 6, 2011 | Reply

5. […] and , respectively, then we say “dominates” — and we write — if dominates for all […]

Pingback by The Dominance Order on Tabloids « The Unapologetic Mathematician | January 10, 2011 | Reply

6. […] the dominance order for row tabloids. Of course, in doing so we have to alter our definition of the dominance order on Ferrers diagrams to take columns into account instead of […]

Pingback by The Column Dominance Order « The Unapologetic Mathematician | January 20, 2011 | Reply