# Dominance order

In discrete mathematics, dominance order (synonyms: dominance ordering, majorization order, natural ordering) is a partial order on the set of partitions of a positive integer n that plays an important role in algebraic combinatorics and representation theory, especially in the context of symmetric functions and representation theory of the symmetric group.

## Definition

If p = (p$_1$,p$_2$,...) and q = (q$_1$,q$_2$,...) are partitions of n, with the parts arranged in the weakly decreasing order, then p precedes q in the dominance order if for any k ≥ 1, the sum of the k largest parts of p is less than or equal to the sum of the k largest parts of q:
    $p\trianglelefteq q{\text{ if and only if }}p_{1}+\cdots +p_{k}\leq q_{1}+\cdots +q_{k}{\text{ for all }}k\geq 1.$
In this definition, partitions are extended by appending zero parts at the end as necessary.

## Properties of the dominance ordering

* Among the partitions of n, (1,...,1) is the smallest and (n) is the largest.
* The dominance ordering implies lexicographical ordering, i.e. if p dominates q and p ≠ q, then for the smallest i such that p$_i$ ≠ q$_i$ one has p$_i$ > q$_i$.
* The poset of partitions of n is linearly ordered (and is equivalent to lexicographical ordering) if and only if n ≤ 5. It is graded if and only if n ≤ 6. See image at right for an example.
* A partition p covers a partition q if and only if p$_i$ = q$_i$ + 1, p$_k$ = q$_k$ − 1, p$_j$ = q$_j$ for all j ≠ i,k and either (1) k = i + 1 or (2) q$_i$ = q$_k$ (Brylawski, Prop. 2.3). Starting from the Young diagram of q, the Young diagram of p is obtained from it by first removing the last box of row k and then appending it either to the end of the immediately preceding row k − 1, or to the end of row i < k if the rows i through k of the Young diagram of q all have the same length.
* Every partition p has a conjugate (or dual) partition p′, whose Young diagram is the transpose of the Young diagram of p. This operation reverses the dominance ordering:
       $p\trianglelefteq q$ if and only if $q^{\prime }\trianglelefteq p^{\prime }.$
* The dominance ordering determines the inclusions between the Zariski closures of the conjugacy classes of nilpotent matrices.

## 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:
    ${\hat {p}}=(0,p_{1},p_{1}+p_{2},\ldots ,p_{1}+p_{2}+\cdots +p_{n}).$
The partition p can be recovered from its associated (n+1)-tuple by applying the step 1 difference, $p_{i}={\hat {p}}_{i}-{\hat {p}}_{i-1}.$ 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, ${\hat {p}}_{i}\leq {\hat {p}}_{i+1};$
* Concave, $2{\hat {p}}_{i}\geq {\hat {p}}_{i-1}+{\hat {p}}_{i+1};$
* The initial term is 0 and the final term is n, ${\hat {p}}_{0}=0,{\hat {p}}_{n}=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 $r\trianglelefteq p,r\trianglelefteq q$ if and only if ${\hat {r}}\leq {\hat {p}},{\hat {r}}\leq {\hat {q}}.$ 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 $\operatorname {min} ({\hat {p}}_{i},{\hat {q}}_{i}).$ 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 [3,1,1,1] and [2,2,2] 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′:
    $p\lor q=(p^{\prime }\land q^{\prime })^{\prime }.$
For the two partitions p and q in the preceding example, their conjugate partitions are [4,1,1] and [3,3] with meet [3,2,1], which is self-conjugate; therefore, the join of p and q is [3,2,1].
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.

## Generalizations

Partitions of n can be graphically represented by Young diagrams on n boxes. Standard Young tableaux are certain ways to fill Young diagrams with numbers, and a partial order on them (sometimes called the dominance order on Young tableaux) can be defined in terms of the dominance order on the Young diagrams. For a Young tableau T to dominate another Young tableau S, the shape of T must dominate that of S as a partition, and moreover the same must hold whenever T and S are first truncated to their sub-tableaux containing entries up to a given value k, for each choice of k.
Similarly, there is a dominance order on the set of standard Young bitableaux, which plays a role in the theory of standard monomials.