Dominance order on partitions

Let $\lambda ,\mu ⊢n$ be partitions of the same integer $n$ (Partitions, English diagrams, and conjugation). We say that $\lambda$ dominates $\mu$, and write $\lambda ⊵\mu$, exactly when ${\sum }_{i=1}^r{\lambda }_i\ge {\sum }_{i=1}^r{\mu }_i\text{for every }r\ge 1,$ where each sequence is padded with zeros beyond its number of parts; since both partitions have total $n$, both sides equal $n$ for all $r$ at least the number of parts of either, so the condition is a finite family of inequalities between integers. We write $\lambda ⊳\mu$ when $\lambda ⊵\mu$ and $\lambda \mathrm{\ne }\mu$. The relation $⊵$ is the dominance order on the partitions of $n$; we call $\lambda$ and $\mu$ incomparable when neither $\lambda ⊵\mu$ nor $\mu ⊵\lambda$ holds.

Because it is defined by a family of non-strict inequalities between integers, $⊵$ is reflexive and transitive. It is also antisymmetric: if $\lambda ⊵\mu$ and $\mu ⊵\lambda$, then the prefix sums of $\lambda$ and of $\mu$ are equal for every $r\ge 1$, and subtracting consecutive prefix sums gives ${\lambda }_i={\mu }_i$ for every $i$ (both sequences are eventually zero). Hence $⊵$ is a partial order on the set of partitions of $n$. For $n\ge 1$, the partition $(n)$ is its unique maximum and the partition $(1^n)$ its unique minimum: for every $\mu ⊢n$ and every $r\ge 1$ one has $\min (r,n)={\sum }_{i\le r}(1^n{)}_i\le {\sum }_{i\le r}{\mu }_i\le n={\sum }_{i\le r}(n{)}_i\mathrm{.}$

For $n=0$ the order is the trivial order on the one-element set $\{\mathrm{\varnothing }\}$.

• Partial, not total. Dominance is in general a proper partial order, not a total order: the partitions $(4,1,1)$ and $(3,3)$ of $6$ are incomparable, because their prefix sums $4,5,6$ and $3,6,6$ cross, and so are their conjugates $(3,1,1,1)$ and $(2,2,2)$. For each $n\le 5$, by contrast, all partitions of $n$ are comparable. The companion examples page lists the chains through size five and this first incomparable pair.

• Not the lexicographic order. Dominance must not be identified with the lexicographic order on partitions, which orders $\lambda$ and $\mu$ by their first differing part and is total. The two relations agree on all partitions of $n$ for $n\le 5$, but lexicographic order is total by definition while dominance is not, so the relations are distinct; a dominance step never follows from a comparison of single parts alone, only from all the prefix sums.

• Conjugation reverses the order. Transposing diagrams turns prefix sums of row lengths into prefix sums of column heights, and this reverses dominance: $\lambda ⊵\mu$ holds if and only if ${\mu }^{\mathrm{\prime }}⊵{\lambda }^{\mathrm{\prime }}$. This is proved on this page as Conjugation reverses dominance and is used to keep row and column versions of every later statement consistent.