In mathematics, especially order theory, the interval order for a collection of intervals on the real line is the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2. More formally, a countable poset P = ( X , ≤ ) {\displaystyle P=(X,\leq )} is an interval order if and only if there exists a bijection from X {\displaystyle X} to a set of real intervals, so x i ↦ ( ℓ i , r i ) {\displaystyle x_{i}\mapsto (\ell _{i},r_{i})} , such that for any x i , x j ∈ X {\displaystyle x_{i},x_{j}\in X} we have
x i < x j {\displaystyle x_{i}<x_{j}} in P {\displaystyle P} exactly when r i < ℓ j {\displaystyle r_{i}<\ell _{j}} . Such posets may be equivalently characterized as those with no induced subposet isomorphic to the pair of two-element chains, in other words as the ( 2 + 2 ) {\displaystyle (2+2)} -free posets. Fully written out, this means that for any two pairs of elements a > b {\displaystyle a>b} and c > d {\displaystyle c>d} one must have a > d {\displaystyle a>d} or c > b {\displaystyle c>b} . The subclass of interval orders obtained by restricting the intervals to those of unit length, so they all have the form ( ℓ i , ℓ i + 1 ) {\displaystyle (\ell _{i},\ell _{i}+1)} , is precisely the semiorders. The complement of the comparability graph of an interval order ( X {\displaystyle X} , ≤) is the interval graph ( X , ∩ ) {\displaystyle (X,\cap )} . Interval orders should not be confused with the interval-containment orders, which are the inclusion orders on intervals on the real line (equivalently, the orders of dimension ≤ 2). Interval orders' practical applications include modelling evolution of species and archaeological histories of pottery styles.
Interval orders and dimension
An important parameter of partial orders is order dimension: the dimension of a partial order P {\displaystyle P} is the least number of linear orders whose intersection is P {\displaystyle P} . For interval orders, dimension can be arbitrarily large. And while the problem of determining the dimension of general partial orders is known to be NP-hard, determining the dimension of an interval order remains a problem of unknown computational complexity. A related parameter is interval dimension, which is defined analogously, but in terms of interval orders instead of linear orders. Thus, the interval dimension of a partially ordered set P = ( X , ≤ ) {\displaystyle P=(X,\leq )} is the least integer k {\displaystyle k} for which there exist interval orders ⪯ 1 , … , ⪯ k {\displaystyle \preceq _{1},\ldots ,\preceq _{k}} on X {\displaystyle X} with x ≤ y {\displaystyle x\leq y} exactly when x ⪯ 1 y , … , {\displaystyle x\preceq _{1}y,\ldots ,} and x ⪯ k y {\displaystyle x\preceq _{k}y} . The interval dimension of an order is never greater than its order dimension.
Combinatorics In addition to being isomorphic to ( 2 + 2 ) {\displaystyle (2+2)} -free posets, unlabeled interval orders on [ n ] {\displaystyle [n]} are also in bijection with a subset of fixed-point-free involutions on ordered sets with cardinality 2 n {\displaystyle 2n} . These are the involutions with no so-called left- or right-neighbor nestings where, for any involution
… excerpt ends here. Continue reading the full article.
