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 and so that neither nor . 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, if for some we have for all , and .
As an example, here’s the lexicographic order on the partitions of :
Now, comparing this order to the dominance order, we notice that they’re almost the same. Specifically, every time , we find as well.
If , then this is trivially true. But if there must be at least one with . Let be the first such index. Now we find that
This inequality must go in this direction since . We conclude that , and so in the lexicographic order.
No comments yet.