Dominance order
From Wikipedia, the free encyclopedia
Dominance order (synonyms: dominance ordering, majorization order) 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.
Contents |
[edit] Definition
If p1,p2,… and q1,q2,… 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:
if and only if 
for all 
[edit] Properties of the dominance ordering
- Among the partitions of n, (1,…1) is the smallest and (n) is the largest.
- The poset of partitions of n is linearly ordered (or a chain) if and only if n ≤ 5 and is graded if only if n ≤ 6.
- The dominance ordering is stronger than (i.e. implies) the lexicographical ordering.
- Covering relations are given by the pairs p, q of partitions which differ only in two consecutive parts such that qi = pi + 1 and qi + 1 = pi + 1 − 1.
- Partitions of n form a lattice under the dominance ordering and the operation of conjugation is an antiautomorphism of this lattice. Thus the dominance ordering can be also defined in terms of the dual partitions.
- Dominance ordering determines the inclusions between the Zariski closures of the conjugacy classes of nilpotent matrices.
[edit] Generalizations
Partitions of n can be graphically represented by Young diagrams on n boxes. The set of standard Young tableaux extends the set of Young diagrams and admits a partial order (sometimes called the dominance order on Young tableaux) that extends the dominance order on the Young diagrams. Similarly, there is a dominance order on the set of standard Young bitableaux, which plays a role in the theory of standard monomials.
[edit] See also
[edit] References
- Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, 1979 ISBN 0-19-853530-9
- Richard P. Stanley, Enumerative Combinatorics, Volume 2. Cambridge University Press, 1999 ISBN 0-521-56069-1
- Thomas Brylawski, The lattice of integer partitions, Discrete Mathematics, vol. 6, no. 3, 1973, pp. 201–219
