---
tag: 9MMG0335JE
kind: statement
role: theorem
name: Fishburn's theorem on interval orders
msc: [06A06, 06A07]
uses: [60FNZ35H6R, VSNQV29KFJ]
about: [VSNQV29KFJ]
sources:
  - url: https://en.wikipedia.org/wiki/Interval_order
---

## Statement

Let $(P, <)$ be a finite [[strict partial order|60FNZ35H6R]].
Then $P$ is an [[interval order|VSNQV29KFJ]] if and only if $P$ contains no $\mathbf{2} + \mathbf{2}$.
Being an interval order means that there are real intervals $[l_x, r_x]$, for $x \in P$, with $x < y$ if and only if $r_x < l_y$.
Here $P$ contains a $\mathbf{2} + \mathbf{2}$ when there are $a < b$ and $c < d$ in $P$ with $a$ incomparable to $d$ and $c$ incomparable to $b$.

## 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}$.

## Explanations

### L1 human

Think of events that each take up a time interval, with one event before another when it ends before the other starts.
The orders that arise this way are the interval orders.
Fishburn's theorem says that one small pattern is the only obstacle: two pairs $a$ before $b$ and $c$ before $d$, where $a$ overlaps $d$ and $c$ overlaps $b$.
Intervals on a line cannot do this, and every order that avoids it can be drawn with intervals.

### L2 human

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.