Inductive characterizations of finite interval orders and semiorders
type: Item
instance of: scholarly article
title: Inductive characterizations of finite interval orders and semiorders
zbMATH Open document ID: 1178.06003
author: Jimmy Leblet
author: Jean-Xavier Rampon
published in: Order
publication date: 2009-09-14T00:00:00Z
review text: 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\)).
reviewed by: Egbert Harzheim
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 5603898
zbMATH Keywords: antichain
zbMATH Keywords: characterization
zbMATH Keywords: decomposition
zbMATH Keywords: finite order
zbMATH Keywords: inductive definition
zbMATH Keywords: interval order
zbMATH Keywords: partially ordered sets
zbMATH Keywords: semiorder
MaRDI profile type: Publication
full work available at URL: s11083-009-9125-9
OpenAlex ID: W2057127470
cites work: Intransitive indifference with unequal indifference intervals
cites work: Q3344239
cites work: Semiorders and a Theory of Utility Discrimination
cites work: Description of some relations on the set of real-line intervals
cites work: Q4791727
cites work: Foundational aspects of theories of measurement
cites work: Q4004146
DOI: 10.1007/S11083-009-9125-9
description: scientific article; zbMATH DE number 5603898