Fishburn's theorem on interval orders

Remarks

One direction is direct. If intervals represent $P$ and $a < b$, $c < d$, then $r_a < l_b$ and $r_c < l_d$; if also $a \not< d$ and $c \not< b$, then $l_d \le r_a$ and $l_b \le r_c$, so $r_a < l_b \le r_c < l_d \le r_a$, a contradiction. For the converse, the absence of $\mathbf{2} + \mathbf{2}$ means that the sets of predecessors $\set{y : y < x}$ are totally ordered by inclusion, and so are the sets of successors. List the distinct predecessor sets as $D_1 \subsetneq D_2 \subsetneq \cdots \subsetneq D_k$. Let $l_x$ be the index of the predecessor set of $x$, and let $r_x$ be the largest $j$ with $x \notin D_j$. Then $x < y$ means $x \in D_{l_y}$, which happens exactly when $r_x < l_y$.

Example: the four elements $a < b$, $c < d$ with no other relations form a $\mathbf{2} + \mathbf{2}$, so they cannot be represented by intervals. The order on three intervals $[0, 1]$, $[2, 3]$, $[0, 3]$ has the single relation $[0,1] < [2,3]$ and contains no $\mathbf{2} + \mathbf{2}$.

Going deeper

For a student

The theorem is a forbidden-subposet characterization, like the characterization of semiorders by the absence of $\mathbf{2} + \mathbf{2}$ and $\mathbf{3} + \mathbf{1}$. It shows that interval orders are exactly the posets whose strict down-sets form a chain under inclusion, which gives a fast test for being an interval order. Interval orders are the orders whose incomparability graphs are interval graphs, so the theorem connects order theory with the theory of interval graphs.