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","p",…) and "q" = ("q","q",…) 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": In this definition, partitions are extended by appending zero parts at the end as necessary. Lattice structure. Partitions of "n" form a lattice under the dominance ordering, denoted "L", 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, formula_5 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: 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 formula_9 if and only if formula_10 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  formula_11 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"′: 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", such as the minimal height and the maximal covering number, and classified the intervals of small length. While "L" 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".