Dominance Order - Lattice Structure

Lattice Structure

Partitions of n form a lattice under the dominance ordering, denoted L_n, and the operation of conjugation is an antiautomorphism of this lattice. To explicitly describe the lattice operations, for each partition p consider the associated (n + 1)-tuple:

The partition p can be recovered from its associated (n+1)-tuple by applying the step 1 difference, Moreover, the (n+1)-tuples associated to partitions of n are characterized among all integer sequences of length n + 1 by the following three properties:

• Nondecreasing,
• Concave,
• The initial term is 0 and the final term is n,

By the definition of the dominance ordering, partition p precedes partition q if and only if the associated (n + 1)-tuple of p is term-by-term less than or equal to the associated (n + 1)-tuple of q. If p, q, r are partitions then if and only if The componentwise minimum of two nondecreasing concave integer sequences is also nondecreasing and concave. Therefore, for any two partitions of n, p and q, their meet is the partition of n whose associated (n + 1)-tuple has components The natural idea to use a similar formula for the join fails, because the componentwise maximum of two concave sequences need not be concave. For example, for n = 6, the partitions and have associated sequences (0,3,4,5,6,6,6) and (0,2,4,6,6,6,6), whose componentwise maximum (0,3,4,6,6,6,6) does not correspond to any partition. To show that any two partitions of n have a join, one uses the conjugation antiautomorphism: the join of p and q is the conjugate partition of the meet of p′ and q′:

For the two partitions p and q in the preceding example, their conjugate partitions are and with meet, which is self-conjugate; therefore, the join of p and q is .

Thomas Brylawski has determined many invariants of the lattice L_n, such as the minimal height and the maximal covering number, and classified the intervals of small length. While L_n is not distributive for n ≥ 7, it shares some properties with distributive lattices: for example, its Möbius function takes on only values 0, 1, −1.