Linear extension

Definitions

Linear extension of a partial order

A partial order is a reflexive, transitive and antisymmetric relation. Given any partial orders ,\leq, and ,\leq^, on a set X, ,\leq^, is a linear extension of ,\leq, exactly when

1. ,\leq^*, is a total order, and
2. For every x, y \in X, if x \leq y, then x \leq^* y.

It is that second property that leads mathematicians to describe ,\leq^*, as extending ,\leq.

Alternatively, a linear extension may be viewed as an order-preserving bijection from a partially ordered set P to a chain C on the same ground set.

Linear extension of a preorder

A preorder is a reflexive and transitive relation. The difference between a preorder and a partial-order is that a preorder allows two different items to be considered "equivalent", that is, both x\precsim y and y\precsim x hold, while a partial-order allows this only when x=y. A relation \precsim^* is called a linear extension of a preorder \precsim if:

1. \precsim^* is a total preorder, and
2. For every x, y \in X, if x\precsim y then x\precsim^* y , and
3. For every x, y \in X, if x\prec y then x\prec^* y . Here, x\prec y means "x \precsim y and not y \precsim x". The difference between these definitions is only in condition 3. When the extension is a partial order, condition 3 need not be stated explicitly, since it follows from condition 2. Proof: suppose that x \precsim y and not y \precsim x. By condition 2, x\precsim^* y. By reflexivity, "not y \precsim x" implies that y\neq x. Since \precsim^ is a partial order, x\precsim^ y and y\neq x imply "not y\precsim^ x". Therefore, x\prec^ y.

However, for general preorders, condition 3 is needed to rule out trivial extensions. Without this condition, the preorder by which all elements are equivalent (y \precsim x and x \precsim y hold for all pairs x,y) would be an extension of every preorder.

Order-extension principle

The statement that every partial order can be extended to a total order is known as the order-extension principle. A proof using the axiom of choice was first published by Edward Marczewski (Szpilrajin) in 1930. Marczewski writes that the theorem had previously been proven by Stefan Banach, Kazimierz Kuratowski, and Alfred Tarski, again using the axiom of choice, but that the proofs had not been published.{{citation

There is an analogous statement for preorders: every preorder can be extended to a total preorder. This statement was proved by Hansson.

In modern axiomatic set theory the order-extension principle is itself taken as an axiom, of comparable ontological status to the axiom of choice. The order-extension principle is implied by the Boolean prime ideal theorem or the equivalent compactness theorem,{{citation | orig-year=originally published in 1973

Applying the order-extension principle to a partial order in which every two elements are incomparable shows that (under this principle) every set can be linearly ordered. This assertion that every set can be linearly ordered is known as the ordering principle, OP, and is a weakening of the well-ordering theorem. However, there are models of set theory in which the ordering principle holds while the order-extension principle does not.{{citation | editor1-last = Scott | editor1-first = Dana S. | editor2-last = Jech | editor2-first = Thomas J.

Related results

The order extension principle is constructively provable for finite sets using topological sorting algorithms, where the partial order is represented by a directed acyclic graph with the set's elements as its vertices. Several algorithms can find an extension in linear time.{{citation | doi-access = free

The order dimension of a partial order is the minimum cardinality of a set of linear extensions whose intersection is the given partial order; equivalently, it is the minimum number of linear extensions needed to ensure that each critical pair of the partial order is reversed in at least one of the extensions.

Antimatroids may be viewed as generalizing partial orders; in this view, the structures corresponding to the linear extensions of a partial order are the basic words of the antimatroid.{{citation | author2-link = Günter M. Ziegler | editor-last = White | editor-first = Neil

This area also includes one of order theory's most famous open problems, the 1/3–2/3 conjecture, which states that in any finite partially ordered set P that is not totally ordered there exists a pair (x, y) of elements of P for which the linear extensions of P in which x number between 1/3 and 2/3 of the total number of linear extensions of P.{{citation

Algebraic combinatorics

Counting the number of linear extensions of a finite poset is a common problem in algebraic combinatorics. This number is given by the leading coefficient of the order polynomial multiplied by |P|!.

Young diagrams can be considered a finite order-ideal in the infinite poset \N \times \N. Similarly, standard Young tableaux can be considered as linear extensions of a poset corresponding to the Young diagram. For the (usual) Young diagrams, linear extensions are counted by the hook length formula. For the skew Young diagrams, linear extensions are counted by a determinantal formula.{{citation

References

References

1. Hansson, Bengt. (1968). "Choice Structures and Preference Relations". Synthese.
2. [[Sergey Kislitsyn. (1968). "Finite partially ordered sets and their associated sets of permutations". Matematicheskie Zametki.