Bipartite tolerance orders (Q1336645): Difference between revisions

The paper studies orders which are generalizations of the interval order. An ordered set \(P\) is called a bounded bitolerance order, if for each \(x\in P\) there exists a closed interval \(I_ x= [a(x), d(x)]\) (probably on the set of all real numbers, although this is not explicitly said) and two points \(b(x)\) and \(c(x)\) in \(I_ x\) such that \(x\prec y\) in \(P\) if and only if \(d(x)< b(y)\) and \(a(y)> c(x)\). Further concepts are defined: unit tolerance order, 50\% tolerance order, unit bitolerance order, proper tolerance order, totally bounded tolerance order, bounded tolerance order, totally bounded bitolerance order. An ordered set is bipartite, if it has no three pairwise comparable elements. The main theorem states that for a bipartite ordered set \(P\) all conditions to be some of the mentioned orders are equivalent and a characterization of bipartite ordered sets satisfying these conditions is given. It is stated that there exists a polynomial time algorithm for recognizing whether these conditions are satisfied.