Coxeter Group - Partial Orders

Partial Orders

A choice of reflection generators gives rise to a length function l on a Coxeter group, namely the minimum number of uses of generators required to express a group element; this is precisely the length in the word metric in the Cayley graph. An expression for v using l(v) generators is a reduced word. For example, the permutation (13) in S3 has two reduced words, (12)(23)(12) and (23)(12)(23). The function defines a map generalizing the sign map for the symmetric group.

Using reduced words one may define three partial orders on the Coxeter group, the (right) weak order, the absolute order and the Bruhat order (named for François Bruhat). An element v exceeds an element u in the Bruhat order if some (or equivalently, any) reduced word for v contains a reduced word for u as a substring, where some letters (in any position) are dropped. In the weak order, v ≥ u if some reduced word for v contains a reduced word for u as an initial segment. Indeed, the word length makes this into a graded poset. The Hasse diagrams corresponding to these orders are objects of study, and are related to the Cayley graph determined by the generators. The absolute order is defined analogously to the weak order, but with generating set/alphabet consisting of all conjugates of the Coxeter generators.

For example, the permutation (1 2 3) in S3 has only one reduced word, (12)(23), so covers (12) and (23) in the Bruhat order but only covers (12) in the weak order.

Read more about this topic:  Coxeter Group

Other articles related to "partial orders, order, partial order":

Birkhoff's Representation Theorem - Functoriality
... Birkhoff's theorem, as stated above, is a correspondence between individual partial orders and distributive lattices ... However, it can also be extended to a correspondence between order-preserving functions of partial orders and bounded homomorphisms of the corresponding distributive lattices ... Let 2 denote the partial order on the two-element set {0, 1}, with the order relation 0 < 1, and (following Stanley) let J(P) denote the distributive lattice of lower sets of a ...
Order Dimension Two
... The partial orders with order dimension two may be characterized as the partial orders whose comparability graph is the complement of the comparability graph of a different partial order (Baker, Fishburn ... That is, P is a partial order with order dimension two if and only if there exists a partial order Q on the same set of elements, such that every pair x, y of distinct elements is ... If P is realized by two linear extensions, then partial order Q complementary to P may be realized by reversing one of the two linear extensions ...
Linear Extension - Related Results
... The algorithmic problem of constructing a linear extension of a partial order on a finite set, represented by a directed acyclic graph with the set's elements as its vertices, is known as ... a single linear extension, the problem of counting all linear extensions of a finite partial order is #P-complete however, it may be estimated by a fully polynomial-time randomized ... Among all partial orders with a fixed number of elements and a fixed number of comparable pairs, the partial orders that have the largest number of linear extensions are ...

Famous quotes containing the words orders and/or partial:

    Let’s start with the three fundamental Rules of Robotics.... We have: one, a robot may not injure a human being, or, through inaction, allow a human being to come to harm. Two, a robot must obey the orders given it by human beings except where such orders would conflict with the First Law. And three, a robot must protect its own existence as long as such protection does not conflict with the First or Second Laws.
    Isaac Asimov (1920–1992)

    Both the man of science and the man of art live always at the edge of mystery, surrounded by it. Both, as a measure of their creation, have always had to do with the harmonization of what is new with what is familiar, with the balance between novelty and synthesis, with the struggle to make partial order in total chaos.... This cannot be an easy life.
    J. Robert Oppenheimer (1904–1967)