The Hasse diagram for a partial order alongside an interval representation of the order.
A partial order on the set {a, b, c, d, e, f} illustrated by its Hasse diagram (left) and a collection of intervals that represents it (right).
The ( 2 + 2 ) {\displaystyle (2+2)} poset (black Hasse diagram) cannot be part of an interval order: if a is completely right of b, and d overlaps with both a and b, and c is completely right of d, then c must be completely right of b (light gray edge).

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 archeological histories of pottery styles.[example needed]

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 f {\displaystyle f} on [ 2 n ] {\displaystyle [2n]}, a left nesting is an i ∈ [ 2 n ] {\displaystyle i\in [2n]} such that i < i + 1 < f ( i + 1 ) < f ( i ) {\displaystyle i<i+1<f(i+1)<f(i)} and a right nesting is an i ∈ [ 2 n ] {\displaystyle i\in [2n]} such that f ( i ) < f ( i + 1 ) < i < i + 1 {\displaystyle f(i)<f(i+1)<i<i+1}.

Such involutions, according to semi-length, have ordinary generating function

F ( t ) = ∑ n ≥ 0 ∏ i = 1 n ( 1 − ( 1 − t ) i ) . {\displaystyle F(t)=\sum _{n\geq 0}\prod _{i=1}^{n}(1-(1-t)^{i}).}

The coefficient of t n {\displaystyle t^{n}} in the expansion of F ( t ) {\displaystyle F(t)} gives the number of unlabeled interval orders of size n {\displaystyle n}. The sequence of these numbers (sequenceA022493in theOEIS) begins

1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, …

Notes

Further reading

  • Fishburn, Peter (1985), Interval Orders and Interval Graphs: A Study of Partially Ordered Sets, John Wiley