“Linear extension”的意思、由来-开放百科全书

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

Given any partial orders ≤ and ≤^* on a set X, ≤^* is a linear extension of ≤ exactly when (1) ≤^* is a total order and (2) for every x and y in X, if {{nowrap|x ≤ y}}, then {{nowrap|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 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,^[2] but the reverse implication doesn't hold.^[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 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.^[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]^[7] 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.^[8]

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.

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 {{nowrap|x < y}} number between 1/3 and 2/3 of the total number of linear extensions of P.^[10]^[11] 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 {{nowrap|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.^[12]

References

1. ^{{citation | last = Marczewski | first = Edward | authorlink = Edward Marczewski | journal = Fundamenta Mathematicae | language = French | pages = 386–389 | title = Sur l'extension de l'ordre partiel | url = http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf | volume = 16 | year = 1930| doi = 10.4064/fm-16-1-386-389 }}.
2. ^{{citation | last = Jech | first = Thomas | author-link = Thomas Jech | isbn = 978-0-486-46624-8 | origyear=originally published in 1973 | publisher = Dover Publications | title = The Axiom of Choice | year = 2008}}.
3. ^{{citation | last1 = Felgner | first1 = U. | last2 = Truss | first2 = J. K. | date = March 1999 | doi = 10.2307/2586759 | issue = 1 | journal = The Journal of Symbolic Logic | pages = 199–215 | title = The Independence of the Prime Ideal Theorem from the Order-Extension Principle | volume = 64 | jstor = 2586759| citeseerx = 10.1.1.54.8336 }}.
4. ^{{citation | last = Mathias | first = A. R. D. | contribution = The order extension principle | editor1-last = Scott | editor1-first = Dana S. | editor2-last = Jech | editor2-first = Thomas J. | pages = 179–183 | publisher = American Mathematical Society | series = Proceedings of Symposia in Pure Mathematics | title = Axiomatic Set Theory (University of California, Los Angeles, Calif., July 10 – August 5, 1967) | volume = 13 | year = 1971}}.
5. ^{{citation | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson | last3 = Rivest | first3 = Ronald L. | author3-link = Ronald L. Rivest | last4 = Stein | first4 = Clifford | author4-link = Clifford Stein | contribution = Section 22.4: Topological sort | edition = 2nd | isbn = 978-0-262-03293-3 | pages = 549–552 | publisher = MIT Press | title = Introduction to Algorithms | year = 2001| title-link = Introduction to Algorithms }}.
6. ^{{citation | last1 = Brightwell | first1 = Graham R. | last2 = Winkler | first2 = Peter | author2-link = Peter Winkler | doi = 10.1007/BF00383444 | issue = 3 | journal = Order | pages = 225–242 | title = Counting linear extensions | volume = 8 | year = 1991}}
7. ^{{citation | last1 = Bubley | first1 = Russ | last2 = Dyer | first2 = Martin | author2-link = Martin Dyer | doi = 10.1016/S0012-365X(98)00333-1 | journal = Discrete Mathematics | pages =81–88 | title = Faster random generation of linear extensions | volume = 201 | issue = 1–3 | year = 1999}}.
8. ^{{citation | last1 = Fishburn | first1 = Peter C. | author1-link = Peter C. Fishburn | last2 = Trotter | first2 = W. T. | doi = 10.1016/0012-365X(92)90036-F | mr = 1171114 | issue = 1 | journal = Discrete Mathematics | pages = 25–40 | title = Linear extensions of semiorders: a maximization problem | volume = 103 | year = 1992}}.
9. ^{{citation | last1 = Björner | first1 = Anders | last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler | contribution = Introduction to Greedoids | editor-last = White | editor-first = Neil | isbn = 978-0-521-38165-9 | pages = 284–357 | publisher = Cambridge University Press | series = Encyclopedia of Mathematics and its Applications | title = Matroid Applications | volume = 40 | year = 1992}}. See especially item (1) on {{nowrap|p. 294.}}
10. ^{{citation|author=Kislitsyn, S. S.|year=1968|title=Finite partially ordered sets and their associated sets of permutations|journal=Matematicheskiye Zametki|volume=4|pages=511–518}}.
11. ^{{citation | last = Brightwell | first = Graham R. | doi = 10.1016/S0012-365X(98)00311-2 | issue = 1–3 | journal = Discrete Mathematics | pages = 25–52 | title = Balanced pairs in partial orders | volume = 201 | year = 1999}}.
12. ^{{citation | last1 = Brightwell | first1 = G. R. | last2 = Felsner | first2 = S. | last3 = Trotter | first3 = W. T. | doi = 10.1007/BF01110378 | mr = 1368815 | issue = 4 | journal = Order | pages = 327–349 | title = Balancing pairs and the cross product conjecture | volume = 12 | year = 1995| citeseerx = 10.1.1.38.7841 }}.