Proper and unit bitolerance orders and graphs

✍ Scribed by Kenneth P. Bogart; Garth Isaak

• Book ID: 104113885
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 729 KB
• Volume: 181
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00043-5

✦ Synopsis

We say any order ~ is a tolerance order on a set of vertices if we may assign to each vertex x an interval Ix of real numbers and a real number tx called a tolerance in such a way that x~,y if and only if the overlap of Ix and ly is less than the minimum of t~ and ty and the center of I~ is less than the center of Iy. An order is a bitolerance order if and only if there are intervals Ix and real numbers tl(X) and tr(X) assigned to each vertex x in such a way that x-<y if and only if the overlap of lx and ly is less than both tr(X) and q(y) and the center of Ix is less than the center of Iy. A tolerance or bitolerance order is said to be bounded if no tolerance is larger than the length of the corresponding interval. A bounded tolerance 9raph or bitolerance 9raph (also known as a trapezoid 9raph) is the incomparability graph of a bounded tolerance order or bitolerance order. Such a graph or order is called proper if it has a representation using intervals no one of which is a proper subset of another, and it is called unit if it has a representation using only unit intervals. In a recent paper, Bogart, Fishburn, Isaak and Langley (1995) gave an example of proper tolerance graphs that are not unit tolerance graphs. In this paper we show that a bitolerance graph or order is proper if and only if it is unit. For contrast, we give a new view of the construction of Bogart et al. (1995) from an order theoretic point of view, showing how linear programming may be used to help construct proper but not unit tolerance orders.