Linear extension
From Wikipedia, the free encyclopedia
In mathematics, a partial order ≤* on a set X is an extension of a partial order ≤ on X provided that for any elements x1 and x2 of X with x1 ≤ x2, it is also the case that x1 ≤* x2. A linear extension of ≤ is an extension that is a linear order, or total order.
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.
This area also includes one of order theory's most famous open problems, the ⅓–⅔ conjecture, which states that in any partially ordered set P that is not totally ordered there exists a pair 
for which the linear extensions of P in which x < y number between ⅓ and ⅔ of the total number of linear extensions of P.
