Dominance order

Dominance order
Example of dominance ordering of partitions of n. Here, n = 6, nodes are partitions of 6, edges indicate that the upper node dominates the lower node. While this particular partial ordering is graded, this is not true for the dominance ordering on partitions of any number n > 6.

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.

Contents

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:

 p\trianglelefteq q if and only if  p_1+\cdots+p_k \leq q_1+\cdots+q_k 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, then pi \geq qi for all 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 pi = qi + 1, pk = qk − 1, pj = qj for all ji,k and either (1) k = i + 1 or (2) qi = qk (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 Ln, 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+\ldots+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 Ln, such as the minimal height and the maximal covering number, and classified the intervals of small length. While Ln 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

The dominance order on Young tableaux for the partition 6 = 4+2

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.

See also

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Dominance-based rough set approach — (DRSA) is an extension of rough set theory for multi criteria decision analysis (MCDA), introduced by Greco, Matarazzo and Słowiński. [1][2][3] The main change comparing to the classical rough sets is the substitution of the indiscernibility… …   Wikipedia

  • Dominance-based Rough Set Approach — (DRSA) is an extension of rough set theory for Multi Criteria Decision Analysis (MCDA), introduced by Greco, Matarazzo and Słowiński Greco, S., Matarazzo, B., Słowiński, R.: Rough sets theory for multicriteria decision analysis. European Journal… …   Wikipedia

  • Dominance hierarchy — For other uses, see Dominance. A dominance hierarchy (in humans: social hierarchy) is the organization of individuals in a group that occurs when competition for resources leads to aggression. Schjelderup Ebbe, who studied the often cited example …   Wikipedia

  • Dominance (genetics) — For other uses, see Dominance. A pedigree chart shows how genes are inherited. Dominance in genetics is a relationship between two variant forms (alleles) of a single gene, in which one allele masks the effect of the other in influencing some… …   Wikipedia

  • Dominance (ethology) — For other uses, see Dominance. Dominance in the context of biology and anthropology is the state of having high social status relative to one or more other individuals, who react submissively to dominant individuals. This enables the dominant… …   Wikipedia

  • Dominance (economics) — For other uses, see Dominance. For the game theory, see Strategic dominance. Marketing Key concepts …   Wikipedia

  • Dominance and submission — For other uses, see Dominance. A submissive man stretches out his bound wrists. Dominance and submission (also called D s, Ds, and D/s)[1] is a set of behaviors, customs and rituals involving the giving by one individual to another individual of… …   Wikipedia

  • Dominance (game theory) — In game theory, dominance (also called strategic dominance) occurs when one strategy is better than another strategy for one player, no matter how that player s opponents may play. Many simple games can be solved using dominance.The opposite,… …   Wikipedia

  • Dominance signal — A dominance signal is used in a dominance hierarchy or pecking order to indicate an animal s dominance. Dorsal darkening has been suggested to represent a dominance signal in male tree lizards.[1] Gorillas sometimes use chest drumming as a… …   Wikipedia

  • dominance hierarchy — Animal Behav. a system or set of relationships in animal groups that is based on a hierarchical ranking, usually established and maintained by behavior in aggressive encounters: one or a few members hold the highest rank and the others are… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”