Talk: Interval orders and their higher dimensional analogs

Abstract:

A collection of closed intervals on the real line is naturally partially ordered by [a, b] < [c, d] if and only if b < c. A partial order of a set S is called an interval ordering if it is isomorphic to the natural order of some collection of intervals. The isomorphism is called an interval representation. A graph is called an interval graph if it is isomorphic to the intersection graph of a collection of closed intervals on the real line. Interval graphs arose in the study of genetics as a way of attempting to test whether overlap data about gene fragments was consistent with a linear arrangement of the components of genes. Interval orders arise in scheduling problems and the special case of unit interval orders, aka semiorders (having a representation in which all intervals have the same length) arises in mathematical psychology and in statistics.

In this talk we will survey briefy the structure theory of interval orders and unit interval orders, outlining some new proofs of basic theorems. We will then discuss some higher dimensional analogs of interval orders, called tube orders, given by convex polytopes touching each of n mutually parallel lines whose affine span is n-space and lying within the convex hull of these lines. (An orientation of one of the lines defines a natural partial order on the polytopes.) The fundamental questions about interval orders and their relationships with interval graphs have analogs for these higher dimensional generalizations, and a few of these questions actually have answers. We will discuss some of the questions and a few answers.

Back