Interval orders and dimension (Q1970712): Difference between revisions

An interval order is a poset whose elements can be interpreted as bounded closed intervals of the real numbers with intervals \(I<J\) if the right endpoint of \(I\) is to the left of the left endpoint of \(J\) on the real line. At the same time using such an interpretation (non unique) also determines an overlap graph (non unique) where \(I\) and \(J\) overlap if they intersect but neither is contained in the other. Interval orders are a special class of posets which have been well studied and for which many special properties hold which do not hold in general. In this paper another such ``class-dependent'' theorem is proven, viz: for every finite interval order \(X\) there exists a positive integer \(t=t(X)\) such that if \(Y\) is any interval order of dimension at least \(t\), then \(Y\) contains a subposet isomorphic to \(X\). In particular, if \(|X|=n\), then \(t=3n-6\) will work. This shows that interval orders are ``sufficiently scarce'' to admit such a theorem. Trivially, chains and antichains are obviously of the same type with \(t(X)=1\) or 2 respectively. The authors suspect that \(t=3n-6\) is not the best estimate.