Interval Order - Interval Dimension

Interval Dimension

The interval dimension of a partial order can be defined as the minimal number of interval order extensions realizing this order, in a similar way to the definition of the order dimension which uses linear extensions. The interval dimension of an order is always less than its order dimension, but interval orders with high dimensions are known to exist. While the problem of determining the order dimension of general partial orders is known to be NP-complete, the complexity of determining the order dimension of an interval order is unknown.

Read more about this topic:  Interval Order

Famous quotes containing the words dimension and/or interval:

    God cannot be seen: he is too bright for sight; nor grasped: he is too pure for touch; nor measured: for he is beyond all sense, infinite, measureless, his dimension known to himself alone.
    Marcus Minucius Felix (2nd or 3rd cen. A.D.)

    I was interested to see how a pioneer lived on this side of the country. His life is in some respects more adventurous than that of his brother in the West; for he contends with winter as well as the wilderness, and there is a greater interval of time at least between him and the army which is to follow. Here immigration is a tide which may ebb when it has swept away the pines; there it is not a tide, but an inundation, and roads and other improvements come steadily rushing after.
    Henry David Thoreau (1817–1862)