Interval order

2020 Mathematics Subject Classification: Primary: 06A [MSN][ZBL]

interval ordering, interval partially ordered set, interval poset

A partial order on the set $S$ of closed intervals of the real line $\mathbb{R}$, defined by $$ I_1 \le I_2 \Leftrightarrow x \le y\ \text{in}\ \mathbb{R}\ \text{for all}\ x\in I_1,\,y \in I_2\ . $$

Such a partially ordered set (more precisely, one isomorphic to it) is called an interval order.

A linear order, also called a totally ordered set, is an interval order (but an interval order need not be total, of course).

There is the following forbidden sub-poset characterization of interval orders (the Fishburn theorem, [a1]): A poset $P$ is an interval order if and only if $P$ does not contain the disjoint sum $\mathbf{2} + \mathbf{2}$ as a sub-poset (cf. also Disjoint sum of partially ordered sets). Here, $\mathbf{2}$ is the totally ordered set $\{1,2\}$, $1<2$, so that $\mathbf{2} + \mathbf{2} = \{a_1,a_2,b_1,b_2\}$ with $a_1 < a_2$, $b_1 < b_2$ and no other comparable pairs of distinct elements.

A poset is called a semi-order if there is a function $f : P \rightarrow \mathbf{R}$ such that $x < y$ in $P$ if and only if $f(y) > f(x)+1$. Clearly, a semi-order is isomorphic to a unit interval order: an interval order with all intervals of length $1$. Here too, a forbidden sub-poset characterization holds (the Scott–Suppes theorem, [a2]): A poset $P$ is a semi-order if and only if it does not contain either $\mathbf{2} + \mathbf{2}$ or $\mathbf{3} + \mathbf{1}$ as a sub-poset.

References

[a1]	P.C. Fishburn, "Intransitive indifference with unequal indifference intervals" J. Math. Psychol. , 7 (1970) pp. 144–149
[a2]	D. Scott, P. Suppes, "Foundational aspects of the theories of measurement" J. Symbolic Logic , 23 (1958) pp. 113–128
[a3]	W.T. Trotter, "Partially ordered sets" R.L. Graham (ed.) M. Grötschel (ed.) L. Lovász (ed.) , Handbook of Combinatorics , I , North-Holland (1995) pp. 433–480
[b1]	Martin Charles Golumbic, Ann N. Trenk, "Tolerance Graphs", Cambridge Studies in Advanced Mathematics 89 Cambridge University Press (2004) ISBN 0-521-82758-2