Structural Considerations for Interval Orders with Length Constraints

A partially ordered set (poset), P =(X;<), is a set X together with a relation, <,that is irreexive and transitive. An interval order is a poset which has an intervalrepresentation: an assignment of a closed interval, I_x, in the real number line toeach x in X so that x<y if and only if I_x is completely to the left of I_y. Wienerand Fishburn characterized interval orders as posets which do not contain a 2+2as an induced suborder [5, 22]. Define P[p, q] to be posets for which there existsan interval representation with interval lengths in [p, q]. We will consider p and qto be positive integers. Scott and Suppes characterize P[1, 1] as posets which donot contain a 2+2 or a 3+1 as induced suborders, and Fishburn generalizes thisresult to characterize P[1, q] as posets which do not contain a 2+2 or a (q+2)+1 asinduced suborders [20, 8]. We use the weighted digraph techniques of [2] to developcomplete lists of minimal forbidden substructures for P[2, q] and P[3, q] and partiallists for P[p, q]. We also relate P[p, kp+1] and P[p+1, k(p+1)+1] and give a list ofrelationships for structures in P[p, q].