On realizable biorders and the biorder dimension of a relation (Q1057213)

A binary relation R is biorder if for all a, b, d, e: \[ a R d\wedge b R e\to a R e\vee b R d. \] The problem of representation of an arbitrary relation by the intersection (union) of a collection of biorders is considered. The concept of bidimension is introduced for choosing the smallest one of such a collection. The connection of this concept with those of dimension of a partial order and interval dimension of a strict partial order is investigated. It is proved that the bidimension of a relation R is equal to the chromatic number of a certain associated hypergraph. To any relation is associated a distinguished quasi-order and it is shown that the dimension of that quasi-order is equal to the bidimension. The applications of the obtained results to multidimensional scaling are discussed. It is shown how the various scales are associated to the biorders forming a minimal representation.