The Unapologetic Mathematician

Mathematics for the interested outsider

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 ith 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 Posted by | Algebra, Representation Theory, Representations of Symmetric Groups | 6 Comments