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. 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. 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.
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.
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. 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.
Read more about this topic: Linear Extension
Famous quotes containing the words related and/or results:
“The question of place and climate is most closely related to the question of nutrition. Nobody is free to live everywhere; and whoever has to solve great problems that challenge all his strength actually has a very restricted choice in this matter. The influence of climate on our metabolism, its retardation, its acceleration, goes so far that a mistaken choice of place and climate can not only estrange a man from his task but can actually keep it from him: he never gets to see it.”
—Friedrich Nietzsche (1844–1900)
“Consider what you have in the smallest chosen library. A company of the wisest and wittiest men that could be picked out of all civil countries in a thousand years have set in best order the results of their learning and wisdom. The men themselves were hid and inaccessible, solitary, impatient of interruption, fenced by etiquette; but the thought which they did not uncover in their bosom friend is here written out in transparent words to us, the strangers of another age.”
—Ralph Waldo Emerson (1803–1882)