Finding a Representation of an Interval Order

In this section, we develop an algorithm for finding an interval representation of an interval order. In fact, this algorithm can be applied to any poset. Either it will find an interval representation or it will find a subposet isomorphic to \(\bftwo+\bftwo\). As a consequence, we establish the other half of .

When \(\PXP\) is an interval order and \(n\) is a positive integer, there may be many different ways to represent \(\bfP\) using intervals with integer end points in \([n]\). But there is certainly a least \(n\) for which a representation can be found, and here we see that the representation is unique. The discussion will again make use of the notation for down sets and up sets that we introduced prior to the proof of . As a reminder, we repeat it here. For a poset \(\PXP\) and a subset \(S\subset X\), let \(D(S) = \{y\in X:\) there exists some \(x\in S\) with \(y\lt x\) in \(P\}\). Also, let \(D[S]=D(S)\cup S\). When \(|S|=1\), say \(S=\{x\}\), we write \(D(x)\) and \(D[x]\) rather than \(D(\{x\})\) and \(D[\{x\}]\). Dually, for a subset \(S\subseteq X\), we define \(U(S) = \{y\in X:\) there exists some \(x\in X\) with \(y>x\) in \(P\}\). As before, set \(U[S]=U(S)\cup S\). And when \(S=\{x\}\), we just write \(U(x)\) for \(\{y\in X:x\lt y\) in \(P\}\) .

Let \(\PXP\) be a poset. We start our procedure by finding the following subsets of the ground set: \(\mathcal{D} = \{D(x):x\in X\}\). We then distinguish two cases. In the first case, there are distinct elements \(x\) and \(y\) for which \(D(x)\nsubseteq D(y)\) and \(D(y)\nsubseteq D(x)\). In this case, we choose an element \(z\in D(x)-D(y)\) and an element \(w\in D(y)-D(x)\). It follows that the four elements in \(\{x,y,z,w\}\) form a subposet of \(\bfP\) which is isomorphic to \(\bftwo+\bftwo\).

Our second case is that either \(D(x)\subseteq D(y)\) or \(D(y)\subseteq D(x)\) for all \(x,y\in X\). In this case, we will show that \(\bfP\) is an interval order. Now find the family: \(\mathcal{U} = \{U(x):x\in X\}\). In this case, it is easy to see that we will always have either \(U(x)\subseteq U(y)\) or \(U(y)\subseteq U(x)\) for all \(x,y\in X\).

Consider the poset shown in .

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.