Recall that a partition of some fixed natural number is a list of nonnegative integers such that and such that . For the purposes of this post, the actual number of parts in a partition is irrelevant, and since one can always extend a partition with zeroes we may suppose that all partitions have the same fixed number of parts, let’s say .
We put a relation on the set of all partitions of by declaring if and only if , , and so on. In other words, for every integer ranging from to , the sum of the first parts of must not be greater than the sum of the first parts of . Let’s prove that this is a partial order: it must be reflexive, transitive and antisymmetric.
- Reflexive: this one’s pretty easy.
- Transitive: also easy. Suppose and . That means for each , we have and . We conclude by transitivity of the usual order .
- Antisymmetric: suppose and . The definition of says that, in particular at , we have and , whence from the antisymmetry of . Then at we have and , whence by antisymmetry of and substitution. We can continue in this way (a more rigorous approach would be a proof by induction but I don’t care enough to do it).
This order on the set of partitions of is called the dominance order (French: ordre de dominance). When , this order has incomparable elements; in fact it’s a linear order if and only if . For instance, temporarily suppose and pick and . Since we immediately find . On the other hand, fails to be smaller than , so . Hence these two elements are incomparable in this order.
Recall that any partition represents a Young diagram. For instance, is a partition of that may be drawn as The conjugate of a partition , written , is another partition of obtained by flipping the Young diagram about its antidiagonal. For our previous example, that would be written textually as .
TODO Show that conjugation is an antiautomorphism.
A new way of seeing things
All these sums are annoying sometimes, so here’s an alternative way to see this construction. To any partition we associate the list defined as We call this list the associated list. It has length and is always (weakly) increasing. Moreover, the last term in the list is always and the first is always . Finally, the associated list is concave: for any , we have This fact can be proven by noticing (easy to see or prove by induction); then
Having any list of elements with the above three properties (starts with and ends with , weakly increasing, concave), we can produce another list having elements using the difference operator defined as Because of concavity, the list is weakly decreasing: Also, the list only contains nonnegative integers since is weakly increasing. Finally, the sum of all elements in is precisely because the sum telescopes to be , which is by the first property. In other words, is actually a partition of . It’s not hard to show the operators and are mutual inverses:
The associated list operator furnishes a bijection between the partitions of and the lists of integers which: (i) start with and end with ; (ii) are weakly increasing; and (iii) are concave. The inverse of is the difference operator .
Back to order. From the definition of , we see that if and only if , with the obvious partial order that compares lists “element by element”. Therefore is an order isomorphism.
Write for that set of lists which are concave, etc., with which the set of partitions of is in bijection. For any two , set to be the list defined by: is the minimum between and . This list is still weakly increasing, its first element is still and its last element is still . Moreover, is also concave, so . Because the order on is comparision element by element, this is actually the minimum (in the order theory sense) of and : we can write . Because is an order isomorphism, this gives us a formula for the infimum of two partitions of in the order : For instance, take and . Recall that these elements are not comparable. We have and . Now we compute the minimum in by taking the minimum componentwise: it’s . Using the difference operator to move back into partitions of , we obtain
We don’t have such an easy time applying the same idea to get a supremum, because the maximum componentwise of two lists in is not necessarily another list in . Indeed, it may not be concave: take for instance the componentwise maximum of and , which is , and that’s not concave at . However we can use the fact that the conjugation is an antiautomorphism, that is, an order isomorphism which reverses the order. Anytime we have something like that, the supremum corresponds to the infimum in the image by the antiautomorphism, so we can set:
As an example, let’s compute the supremum of and . We start by computing their conjugates: and . Now to find the infimum of the conjugates, we move into using the operator: and . As discussed before, their minimum in is given by the componentwise minimum, which is . We move back into partitions of using the difference operator, which gives us . Finally we should take the conjugate of this, but in this particular case is autodual. Hence
This shows that the set of partitions of is not only a partial order, but also a lattice, under the dominance order .