Interval order explained

P=(X,\leq)

is an interval order if and only ifthere exists a bijection from

to a set of real intervals,so

x_i\mapsto(\ell_i,r_i)

,such that for any

x_i,x_j\inX

we have

x_i<x_j

exactly when

r_i<\ell_j

Such posets may be equivalentlycharacterized as those with no induced subposet isomorphic to thepair 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

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 (

, ≤)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 archeological histories of pottery styles.

Interval orders and dimension

An important parameter of partial orders is order dimension: the dimension of a partial order

is the least number of linear orders whose intersection is

. 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,\leq)

is the least integer

for which there exist interval orders

\preceq_1,\ldots,\preceq_k

with

x\leqy

exactly when

x\preceq₁y,\ldots,

and

x\preceq_ky

. The interval dimension of an order is never greater than its order dimension.

Combinatorics

In addition to being isomorphic to

(2+2)

-free posets,unlabeled interval orders on

[n]

are also in bijectionwith a subset of fixed-point-free involutions on ordered sets with cardinality

. These are theinvolutions with no so-called left- or right-neighbor nestings where, for any involution

[2n]

, a left nesting isan

i\in[2n]

such that

i<i+1<f(i+1)<f(i)

and a right nesting is an

i\in[2n]

such that

f(i)<f(i+1)<i<i+1

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

F(t)=\sum_n

	n
\prod
	i=1

(1-(1-t)^i).

The coefficient of

tⁿ

in the expansion of

F(t)

gives the number of unlabeled interval orders of size

. The sequence of these numbers begins

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

References

.
.
.
.
.
Book: Davey . B. A. . Priestley . H. A. . Hilary Priestley . Introduction to Lattices and Order . Introduction to Lattices and Order . Cambridge University Press . 2002 . 1990 . 9780521784511 . 2nd.