Linear extension: Difference between revisions

Revision as of 17:27, 16 May 2018

Revision as of 15:09, 10 February 2019

Line 16:

| url = http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf

| volume = 16

| year = 1930| doi = 10.4064/fm-16-1-386-389 }}.</ref>

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]],<ref>{{citation

| last = Jech | first = Thomas | author-link = Thomas Jech

| isbn = 978-0-486-46624-8

| origyear=originally published in 1973

| publisher = [[Dover Publications]]

Line 32:

| journal = The Journal of Symbolic Logic

| pages = 199–215

| publisher = Association for Symbolic Logic

| title = The Independence of the Prime Ideal Theorem from the Order-Extension Principle

| volume = 64

Line 58 ⟶ 57:

| contribution = Section 22.4: Topological sort

| edition = 2nd

| isbn = 978-0-262-03293-73

| pages = 549–552

| publisher = MIT Press

| title = [[Introduction to Algorithms]]

| year = 2001| title-link = Introduction to Algorithms }}.</ref> Despite the ease of finding a single linear extension, the problem of counting all linear extensions of a finite partial order is [[Sharp-P-complete|#P-complete]]; however, it may be estimated by a [[fully polynomial-time randomized approximation scheme]].<ref>{{citation

| last1 = Brightwell | first1 = Graham R.

| last2 = Winkler | first2 = Peter | author2-link = Peter Winkler

Line 77 ⟶ 76:

| doi = 10.1016/S0012-365X(98)00333-1

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]

| pages =81-8881–88

| title = Faster random generation of linear extensions

| volume = 201

| issue = 1–3

| year = 1999}}.</ref> 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 [[semiorder]]s.<ref>{{citation

| last1 = Fishburn | first1 = Peter C. | author1-link = Peter C. Fishburn

Line 110:

| last = Brightwell | first = Graham R.

| doi = 10.1016/S0012-365X(98)00311-2

| issue = 1-31–3

| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]

| pages = 25–52

Line 126:

| title = Balancing pairs and the cross product conjecture

| volume = 12

| year = 1995}}| citeseerx = 10.</ref>1.1.38.7841

}}.</ref>

== References ==