Interval order

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). 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, I 1 , being considered less than another, I 2 , if I 1 is completely to the left of I 2 . More formally, a countable poset P = (X, \leq) is an interval order if and only if there exists a bijection from X to a set of real intervals, so x_i \mapsto (\ell_i, r_i) , such that for any x_i, x_j \in X we have x_i in P exactly when r_i . 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) -free posets. Fully written out, this means that for any two pairs of elements a > b and c > d one must have a > d or c > b . The subclass of interval orders obtained by restricting the intervals to those of unit length, so they all have the form (\ell_i, \ell_i + 1) , is precisely the semiorders. The complement of the comparability graph of an interval order ( X , ≤) is the interval graph (X, \cap) .…

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).]] 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, I 1 , being considered less than another, I 2 , if I 1 is completely to the left of I 2 . More formally, a countable poset P = (X, \leq) is an interval order if and only if there exists a bijection from X to a set of real intervals, so x_i \mapsto (\ell_i, r_i) , such that for any x_i, x_j \in X we have x_i in P exactly when r_i . 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) -free posets. Fully written out, this means that for any two pairs of elements a > b and c > d one must have a > d or c > b . The subclass of interval orders obtained by restricting the intervals to those of unit length, so they all have the form (\ell_i, \ell_i + 1) , is precisely the semiorders. The complement of the comparability graph of an interval order ( X , ≤) is the interval graph (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. 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, \leq) is the least integer k for which there exist interval orders \preceq_1, \ldots, \preceq_k on X with x \leq y exactly when x \preceq_1 y, \ldots, and x \preceq_k y . The interval dimension of an order is never greater than its order dimension. F(t) = \sum_{n \geq 0} \prod_{i = 1}^n (1-(1-t)^i). The coefficient of t^n in the expansion of F(t) gives the number of unlabeled interval orders of size n . The sequence of these numbers begins 1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, …

Notes

References

. . . . .

Further reading

Text derived from https://en.wikipedia.org/w/index.php?oldid=1370729048 under CC BY-SA 4.0; modifications have been made.