Linear extension

Summary

In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order.

Definitions

edit

Linear extension of a partial order

edit

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

  1.   is a total order, and
  2. For every   if   then  

It is that second property that leads mathematicians to describe   as extending  

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

Linear extension of a preorder

edit

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   and   hold, while a partial-order allows this only when  . A relation   is called a linear extension of a preorder   if:

  1.   is a total preorder, and
  2. For every   if   then   , and
  3. For every   if   then   . Here,   means "  and not  ".

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   and not  . By condition 2,  . By reflexivity, "not  " implies that  . Since   is a partial order,   and   imply "not  ". Therefore,  .

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

Order-extension principle

edit

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.[1]

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

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,[3] but the reverse implication doesn't hold.[4]

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.[5]

edit

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.[6] Despite the ease of finding 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 approximation scheme.[7][8] 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 semiorders.[9]

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.[10]

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   that is not totally ordered there exists a pair   of elements of   for which the linear extensions of   in which   number between 1/3 and 2/3 of the total number of linear extensions of  [11][12] An equivalent way of stating the conjecture is that, if one chooses a linear extension of   uniformly at random, there is a pair   which has probability between 1/3 and 2/3 of being ordered as   However, for certain infinite partially ordered sets, with a canonical probability defined on its linear extensions as a limit of the probabilities for finite partial orders that cover the infinite partial order, the 1/3–2/3 conjecture does not hold.[13]

Algebraic combinatorics

edit

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  

Young tableau can be considered as linear extensions of a finite order-ideal in the infinite poset   and they are counted by the hook length formula.

References

edit
  1. ^ Marczewski, Edward (1930), "Sur l'extension de l'ordre partiel" (PDF), Fundamenta Mathematicae (in French), 16: 386–389, doi:10.4064/fm-16-1-386-389.
  2. ^ Hansson, Bengt (1968). "Choice Structures and Preference Relations". Synthese. 18 (4): 443–458. ISSN 0039-7857.
  3. ^ Jech, Thomas (2008) [originally published in 1973], The Axiom of Choice, Dover Publications, ISBN 978-0-486-46624-8.
  4. ^ Felgner, U.; Truss, J. K. (March 1999), "The Independence of the Prime Ideal Theorem from the Order-Extension Principle", The Journal of Symbolic Logic, 64 (1): 199–215, CiteSeerX 10.1.1.54.8336, doi:10.2307/2586759, JSTOR 2586759.
  5. ^ Mathias, A. R. D. (1971), "The order extension principle", in Scott, Dana S.; Jech, Thomas J. (eds.), Axiomatic Set Theory (University of California, Los Angeles, Calif., July 10 – August 5, 1967), Proceedings of Symposia in Pure Mathematics, vol. 13, American Mathematical Society, pp. 179–183.
  6. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.4: Topological sort", Introduction to Algorithms (2nd ed.), MIT Press, pp. 549–552, ISBN 978-0-262-03293-3.
  7. ^ Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order, 8 (3): 225–242, doi:10.1007/BF00383444, S2CID 119697949
  8. ^ Bubley, Russ; Dyer, Martin (1999), "Faster random generation of linear extensions", Discrete Mathematics, 201 (1–3): 81–88, doi:10.1016/S0012-365X(98)00333-1, S2CID 2942330.
  9. ^ Fishburn, Peter C.; Trotter, W. T. (1992), "Linear extensions of semiorders: a maximization problem", Discrete Mathematics, 103 (1): 25–40, doi:10.1016/0012-365X(92)90036-F, MR 1171114.
  10. ^ Björner, Anders; Ziegler, Günter M. (1992), "Introduction to Greedoids", in White, Neil (ed.), Matroid Applications, Encyclopedia of Mathematics and its Applications, vol. 40, Cambridge University Press, pp. 284–357, ISBN 978-0-521-38165-9. See especially item (1) on p. 294.
  11. ^ Kislitsyn, S. S. (1968), "Finite partially ordered sets and their associated sets of permutations", Matematicheskie Zametki, 4: 511–518.
  12. ^ Brightwell, Graham R. (1999), "Balanced pairs in partial orders", Discrete Mathematics, 201 (1–3): 25–52, doi:10.1016/S0012-365X(98)00311-2.
  13. ^ Brightwell, G. R.; Felsner, S.; Trotter, W. T. (1995), "Balancing pairs and the cross product conjecture", Order, 12 (4): 327–349, CiteSeerX 10.1.1.38.7841, doi:10.1007/BF01110378, MR 1368815, S2CID 14793475.