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}

About these ads

December 17, 2010 - Posted by | Algebra, Representation Theory, Representations of Symmetric Groups

6 Comments »

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 392 other followers

%d bloggers like this: