The hierarchy of classes of bounded bitolerance orders
Martin Charles Golumbic, Ann N. Trenk · Cambridge University Press eBooks · 2004
In this chapter we consider the classes of bounded bitolerance orders arranged in a hierarchy in Figure 10.1. We begin by describing the notation and conventions used in Figure 10.1 and justifying the inclusions and equivalences in the hierarchy. In Section 10.3, we restrict attention to bipartite orders. In that setting, the hierarchy collapses and most of the classes are equivalent. Section 10.4 provides the details to show that any example that appears along an edge between two classes provides a separating example between those two classes. Introduction In Section 5.2, we defined subclasses of bounded bitolerance orders by adding restrictions on interval lengths, tolerant points p ( ν ) and q ( ν ), and left and right tolerances. These restrictions are summarized in Table 10.1. The restrictions are listed so that the top entry of each column is the most restrictive, and they are less restrictive as you travel down the column. Each of the three categories of restrictions is independent. Thus, the restrictions can be combined, by taking one from each column, to give 18 classes of bitolerance orders, some of which turn out to be equivalent. In this chapter we often refer to a class by its abbreviation, for example, (1aii) is the class of unit point-core bitolerance orders, and (3ci) is the class of (bounded) tolerance orders.