Interval Order Representation via Shortest Paths

Our goal in this paper is to illustrate how the representation theorems for finite interval orders and semiorders can be seen as special instances of existence results for potentials in digraphs. This viewpoint yields short proofs of the representation theorems and provides a framework for certain types of additional constraints on the intervals. We also use it to obtain a minimax theorem for the minimum number of endpoints in a representation. The techniques are based on techniques used by Peter Fishburn in proving results about bounded representations of interval orders. Interval orders represent the order structure of a collection of intervals. For example, this can be used to model the relations between a set of events each of which occurs over some time interval. Semiorders are a special case where the intervals have the same length. These can be viewed as representing comparisons of values where a relation is noted only if the difference of values is above a certain threshold. We will not go into more detail here as there are many good references describing the various applications of interval orders and semiorders. See for example Fishburn (1985); Luce, Krantz, and Suppes (1971, 1989, 1990); Pirlot and Vincke (1997). See Fishburn (1997) for a good description of some more general models based on intervals.