---
about:
- VSNQV29KFJ
kind: statement
msc:
- 06A06
name: Minimal integer representation of an interval order
role: theorem
sources:
- locator: source/s_posets_intervalorder_findrep.ptx:53
  url: https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_posets_intervalorder_findrep.ptx#L53
tag: D20HMAETQV
uses:
- VSNQV29KFJ
- ETCE287E2R
---

## Statement

Let $P$ be a finite poset on a set $X$ that contains no $\mathbf{2}+\mathbf{2}$. Let $\mathcal{D}$ be the family of distinct strict down sets $\{y : y < x\}$ of elements $x \in X$. Let $\mathcal{U}$ be the family of distinct strict up sets $\{y : y > x\}$ (see [[upper set|ETCE287E2R]]). Both families are chains under inclusion. Order the sets of each family and use their positions to give every $x \in X$ an interval $I(x)$ with integer end points. This is the standard [[interval order|VSNQV29KFJ]] representation of $P$. Then all of these hold.

1. The two families have the same size: $|\mathcal{D}| = |\mathcal{U}|$. Call this number $d$.
2. For each $x \in X$ with $I(x) = [i, j]$, we have $i \le j$.
3. For $x, y \in X$ with $I(x) = [i, j]$ and $I(y) = [k, l]$, we have $x < y$ in $P$ if and only if $j < k$.
4. The number $d$ is the least positive integer such that $P$ has an interval representation with all end points in $\{1, \dots, d\}$. This representation is unique.

## Remarks

Parts 2 and 3 say that the intervals $I(x)$ are genuine intervals and that they encode the order of $P$ exactly. Part 4 says that this representation uses the fewest possible integer values and that nothing else does as well.