Linear extension

Linear extension

In order theory, a branch of mathematics, a linear extension of a partial order is a linear order (or total order) that is compatible with the partial order.

Contents

Definitions

Given any partial orders ≤ and ≤* on a set X, ≤* is a linear extension of ≤ exactly when (1) ≤* is a linear order and (2) for every x and y in X, if xy, then x* y. 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 P to a chain C on the same ground set.

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 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]

In modern axiomatic set theory the order-extension theory 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,[2] but the reverse implication is not provable.[3]

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

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 topological sorting; several algorithms solve it in linear time.[5] 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.[6] 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.[7]

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

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 < y number between 1/3 and 2/3 of the total number of linear extensions of P.[9][10] An equivalent way of stating the conjecture is that, if one chooses a linear extension of P uniformly at random, there is a pair (x,y) which has probability between 1/3 and 2/3 of being ordered as x < y. 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.[11]

References

  1. ^ Marczewski, Edward (1930), "Sur l'extension de l'ordre partiel" (in French), Fundamenta Mathematicae 16: 386–389, http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf .
  2. ^ Jech, Thomas (2008) [originally published in 1973], The Axiom of Choice, Dover Publications, ISBN 0-486-46624-8 .
  3. ^ Felgner, U.; Truss, J. K. (March 1999), "The Independence of the Prime Ideal Theorem from the Order-Extension Principle", The Journal of Symbolic Logic (Association for Symbolic Logic) 64 (1): 199–215, doi:10.2307/2586759, JSTOR 2586759 .
  4. ^ Mathias, A. R. D. (1971), "The order extension principle", in Scott, Dana S.; Jech, Thomas J., Axiomatic Set Theory (University of California, Los Angeles, Calif., July 10 – August 5, 1967), Proceedings of Symposia in Pure Mathematics, 13, American Mathematical Society, pp. 179–183 .
  5. ^ 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 0-262-03293-7 .
  6. ^ Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order 8 (3): 225–242, doi:10.1007/BF00383444 .
  7. ^ 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, MR1171114 .
  8. ^ Björner, Anders; Ziegler, Günter M. (1992), "Introduction to Greedoids", in White, Neil, Matroid Applications, Encyclopedia of Mathematics and its Applications, 40, Cambridge University Press, pp. 284–357, ISBN 9780521381659 . See especially item (1) on p. 294.
  9. ^ Kislitsyn, S. S. (1968), "Finite partially ordered sets and their associated sets of permutations", Matematicheskiye Zametki 4: 511–518 .
  10. ^ Brightwell, Graham R. (1999), "Balanced pairs in partial orders", Discrete Mathematics 201 (1-3): 25–52, doi:10.1016/S0012-365X(98)00311-2 .
  11. ^ Brightwell, G. R.; Felsner, S.; Trotter, W. T. (1995), "Balancing pairs and the cross product conjecture", Order 12 (4): 327–349, doi:10.1007/BF01110378, MR1368815 .

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Continuous linear extension — In functional analysis, it is often convenient to define a linear transformation on a complete, normed vector space X by first defining a linear transformation on a dense subset of X and then extending to the whole space via the theorem below.… …   Wikipedia

  • Extension (mathematics) — In mathematics, the word extension has many uses. See:Analysis* Carathéodory s extension theorem * Continuous linear extension * M. Riesz extension theorem * Krein extension theorem * Hahn Banach theoremAlgebra* Abelian extension * Algebraic… …   Wikipedia

  • linear, or curvilinear, terminal — A type of simple terminal layout that is repeated in a linear extension to provide additional apron frontage, more gates, and more room within the terminal for passenger processing. Examples of linear or gate arrival concept. Linear concept in… …   Aviation dictionary

  • Linear partial information — (LPI) is a method of making decisions based on insufficient or fuzzy information. LPI was introduced in 1970 by Polish Swiss mathematician Edward Kofler (1911 2007) to simplify decision processes. Comparing to other methods the LPI fuzziness is… …   Wikipedia

  • Linear interpolation — is a method of curve fitting using linear polynomials. It is heavily employed in mathematics (particularly numerical analysis), and numerous applications including computer graphics. It is a simple form of interpolation. Lerp is a quasi acronym… …   Wikipedia

  • Linear low-density polyethylene — (LLDPE) is a substantially linear polymer (polyethylene), with significant numbers of short branches, commonly made by copolymerization of ethylene with longer chain olefins. Linear low density polyethylene differs structurally from conventional… …   Wikipedia

  • Linear Tape-Open — (or LTO) is a magnetic tape data storage technology originally developed in the late 1990s as an open standards alternative to the proprietary magnetic tape formats that were available at the time. Seagate, Hewlett Packard, and IBM initiated the… …   Wikipedia

  • Linear regression — Example of simple linear regression, which has one independent variable In statistics, linear regression is an approach to modeling the relationship between a scalar variable y and one or more explanatory variables denoted X. The case of one… …   Wikipedia

  • Linear complex structure — In mathematics, a complex structure on a real vector space V is an automorphism of V that squares to the minus identity, −I. Such a structure on V allows one to define multiplication by complex scalars in a canonical fashion so as to regard V as… …   Wikipedia

  • Linear Pottery culture — LBK redirects here. For other uses, see LBK (disambiguation). Not to be confused with Linear B. Map of European Neolithic at the apogee of Danubian expansion, c. 4500–4000 BC …   Wikipedia

Share the article and excerpts

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