Interval_order Knowpia

Summary

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₁, being considered less than another, I₂, if I₁ is completely to the left of I₂. 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}<x_{j}$ in $P$ exactly when $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)$ -free posets .^[1] 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 and dimension edit

What is the complexity of determining the order dimension of an interval order?

(more unsolved problems in mathematics)

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

P

is the least number of linear orders whose intersection is

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.^[2]

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}

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.^[3]

Combinatorics edit

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 $2n$ .^[4] These are the involutions with no so-called left- or right-neighbor nestings where, for any involution $f$ on $[2n]$ , a left nesting is an $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^[5]

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 (sequence A022493 in the OEIS) begins

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

Notes edit

References edit

Bousquet-Mélou, Mireille; Claesson, Anders; Dukes, Mark; Kitaev, Sergey (2010), "(2+2) free posets, ascent sequences and pattern avoiding permutations", Journal of Combinatorial Theory, Series A, 117 (7): 884–909, arXiv:0806.0666, doi:10.1016/j.jcta.2009.12.007, MR 2652101, S2CID 8677150.
Felsner, S. (1992), Interval Orders: Combinatorial Structure and Algorithms (PDF), Ph.D. dissertation, Technical University of Berlin.
Felsner, S.; Habib, M.; Möhring, R. H. (1994), "On the interplay between interval dimension and dimension" (PDF), SIAM Journal on Discrete Mathematics, 7 (1): 32–40, doi:10.1137/S089548019121885X, MR 1259007.
Fishburn, Peter C. (1970), "Intransitive indifference with unequal indifference intervals", Journal of Mathematical Psychology, 7 (1): 144–149, doi:10.1016/0022-2496(70)90062-3, MR 0253942.
Zagier, Don (2001), "Vassiliev invariants and a strange identity related to the Dedekind eta-function", Topology, 40 (5): 945–960, doi:10.1016/s0040-9383(00)00005-7, MR 1860536.

Summary

Interval orders and dimension edit

Combinatorics edit

Notes edit

References edit

Further reading edit