Weak order of permutations
- Weak order of permutations
In mathematics, the set of permutations on "n" items can be given the structure of a partial order, called the weak order of permutations. The weak order of permutations forms a lattice.
To define this order, consider the items being permuted to be the integers from 1 to "n", and let Inv("u") denote the set of inversions of a permutation "u" for the natural ordering on these items. That is, Inv("u") is the set of ordered pairs ("i", "j") such that 1 ≤ "i" < "j" ≤ "n" and "u"("i") > "u"("j"). Then, in the weak order, we define "u" ≤ "v" whenever Inv("u") ⊆ Inv("v").
The edges of the Hasse diagram of the weak order are given by permutations "u" and "v" such that "u < v" and such that "v" is obtained from "u" by interchanging two consecutive values of "u". These edges form a Cayley graph for the group of permutations that is isomorphic to the skeleton of a permutohedron.
The identity permutation is the minimum element of the weak order, and the permutation formed by reversing the identity is the maximum element.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Order (mathematics) — Contents 1 In algebra 2 In arithmetic 3 In analysis 4 … Wikipedia
List of order theory topics — Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of ordering, providing a framework for saying when one thing is less than or precedes another. An alphabetical list of many… … Wikipedia
List of order topics — This is a list of order topics, by Wikipedia page.An alphabetical list of many notions of order theory can be found in the order theory glossary. See also inequality, extreme value, optimization (mathematics), domain theory.Basic… … Wikipedia
Cyclic order — In mathematics, a cyclic order is a way to arrange a set of objects in a circle.[nb] Unlike most structures in order theory, a cyclic order cannot be modeled as a binary relation a < b . One does not say that east is more clockwise than west.… … Wikipedia
Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… … Wikipedia
List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… … Wikipedia
List of permutation topics — This is a list of topics on mathematical permutations.*Alternating group *Alternating permutation *Bijection *Circular shift *Combination *Cycle index *Cycle notation *Cyclic order *Cyclic permutation *Derangement *Even and odd permutations… … Wikipedia
LINGUISTIC LITERATURE, HEBREW — This article is arranged according to the following outline: introduction foreword the beginning of linguistic literature linguistic literature and its background the development of linguistic literature Foreword: A Well Defined Unit the four… … Encyclopedia of Judaism
Permutohedron — In mathematics, the permutohedron of order n is an ( n − 1) dimensional polytope embedded in an n dimensional space, the vertices of which are formed by permuting the coordinates of the vector (1, 2, 3, ..., n ).Examples* Order 1: A single point … Wikipedia
Germany — /jerr meuh nee/, n. a republic in central Europe: after World War II divided into four zones, British, French, U.S., and Soviet, and in 1949 into East Germany and West Germany; East and West Germany were reunited in 1990. 84,068,216; 137,852 sq.… … Universalium
