# The Unapologetic Mathematician

## The Lexicographic Order on Partitions

The biggest problem with the dominance order is that it’s only a partial order. That is, there are some pairs of partitions $\lambda$ and $\mu$ so that neither $\lambda\trianglerighteq\mu$ nor $\mu\triangleright\lambda$. We sometimes need a total order, and that’s where the lexicographic order comes in.

The lexicographic order gets its name because it’s just like the way we put words in order in the dictionary. We compare the first parts of each partition. If they’re different we use their order, while if they’re the same we break ties with the tails of the partitions. More explicitly, $\lambda<\mu$ if for some $i$ we have $\lambda_j=\mu_j$ for all $j, and $\lambda_i<\mu_i$.

As an example, here’s the lexicographic order on the partitions of $6$: \displaystyle\begin{aligned}(6)&>(5,1)\\&>(4,2)\\&>(4,1,1)\\&>(3,3)\\&>(3,2,1)\\&>(3,1,1,1)\\&>(2,2,2)\\&>(2,2,1,1)\\&>(2,1,1,1,1)\\&>(1,1,1,1,1,1)\end{aligned}

Now, comparing this order to the dominance order, we notice that they’re almost the same. Specifically, every time $\lambda\trianglerighteq\mu$, we find $\lambda>\mu$ as well.

If $\lambda=\mu$, then this is trivially true. But if $\lambda\neq\mu$ there must be at least one $i$ with $\lambda_i\neq\mu_i$. Let $i$ be the first such index. Now we find that $\displaystyle\sum\limits_{j=1}^{i-1}\lambda_j=\sum\limits_{j=1}^{i-1}\mu_j$

and also $\displaystyle\sum\limits_{j=1}^i\lambda_j>\sum\limits_{j=1}^i\mu_j$

This inequality must go in this direction since $\lambda\triangleright\mu$. We conclude that $\lambda_i>\mu_i$, and so $\lambda>\mu$ in the lexicographic order.

December 21, 2010