Inductive characterizations of finite interval orders and semiorders (Q841168)

Let \((P, <)\) be a finite poset. \(P\) is said to be antichain-series decomposable if its ground set \(V(P)\) is the disjoint union of three sets \(X_1\), \(X_2\) and \(Z\) which fulfill (i) \(X_1\) and \(X_2\) are nonvoid, (ii) \(x_1< x_2\) for all \(x_1\in X_1\), \(x_2\in X_2\), and (iii) \(X_2\cup Z\) is an antichain. \(P\) is said to be recursively antichain-series decomposable if either it is an antichain, or it has an antichain-series decomposition, say \((X_1,X_2,Z)\), such that \(X_1\cup Z\) is still recursively antichain-series decomposable. Theorem 1 shows that this is equivalent to: \(P\) has no subset isomorphic to \(2+2\). As a corollary there follows: An order is an interval order iff it is recursively antichain-series decomposable. \(P\) is called recursively full-antichain-series decomposable if either it is an antichain, or it has a full-antichain-series decomposition \((X_1,X_2,Z)\) such that \(X_1\cup Z\) is still recursively full-antichain-series decomposable. Theorem 3 shows that this is equivalent to: \(P\) has no subset of type \(2+2\) or \(3+1\). As a corollary this implies that \(P\) is a semiorder iff it is recursively full-antichain-series decomposable. (A semiorder is here defined as an order which is isomorphic to a set of real intervals of length 1, where \(I_1< I_2\) if the right end of \(I_1\) is less than the left end of \(I_2\)).