Samiksha Jaiswal (Editor)

Interval order

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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 poset P = ( X , ≤ ) is an interval order if and only if there exists a bijection from X to a set of real intervals, so x i ↦ ( ℓ i , r i ) , such that for any x i , x j ∈ X we have x i < x j in P exactly when r i < ℓ j . Such posets may be equivalently characterized as those with no induced subposet isomorphic to the pair of two element chains, the ( 2 + 2 ) free posets .

Contents

The subclass of interval orders obtained by restricting the intervals to those of unit length, so they all have the form ( ℓ i , ℓ i + 1 ) , is precisely the semiorders.

The complement of the comparability graph of an interval order ( X , ≤) is the interval graph ( X , ∩ ) .

Interval orders should not be confused with the interval-containment orders, which are the containment orders on intervals on the real line (equivalently, the orders of dimension ≤ 2).

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-hard, the complexity of determining the order dimension of an interval order is unknown.

Combinatorics

In addition to being isomorphic to ( 2 + 2 ) free posets, unlabeled interval orders on [ n ] are also in bijection with a subset of fixed point free involutions on ordered sets with cardinality 2 n . These are the involutions with no left or right neighbor nestings where, for f an involution on [ 2 n ] , a left nesting is an i ∈ [ 2 n ] such that i < i + 1 < f ( i + 1 ) < f ( i ) and a right nesting is an i ∈ [ 2 n ] such that 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 ) .

Hence the number of unlabeled interval orders of size n is given by the coefficient of t n in the expansion of F ( t ) .

1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, … (sequence A022493 in the OEIS)

Additional reading

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

    • References

    Interval order Wikipedia
    (Text) CC BY-SA