Inductive characterizations of finite interval orders and semiorders
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\)).
- Description of some relations on the set of real-line intervals
- Foundational aspects of theories of measurement
- scientific article; zbMATH DE number 3877239 (Why is no real title available?)
- scientific article; zbMATH DE number 53952 (Why is no real title available?)
- scientific article; zbMATH DE number 1862431 (Why is no real title available?)
- Intransitive indifference with unequal indifference intervals
- Semiorders and a Theory of Utility Discrimination
- On the complexity of interval orders and semiorders
- Simple and simplest semi-orders
- A simple proof characterizing interval orders with interval lengths between 1 and \(k\)
- On induction principles for partial orders
- Interval orders, semiorders and ordered groups
- scientific article; zbMATH DE number 218552 (Why is no real title available?)
- A Note on Candeal and Induráin’s Semiorder Separability Condition
This page was built for publication: Inductive characterizations of finite interval orders and semiorders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q841168)
