Interval orders and dimension
type: Item
instance of: scholarly article
title: Interval orders and dimension
zbMATH Open document ID: 0947.06002
DOI: 10.1016/S0012-365X(99)00178-8
published in: Discrete Mathematics
publication date: 2000-03-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1420385
zbMATH Keywords: embedding
zbMATH Keywords: dimension
zbMATH Keywords: interval order
zbMATH Keywords: overlap graph
author: H. A. Kierstead
author: William T. Trotter
reviewed by: J. Neggers
MaRDI profile type: Publication
Recommended article: Dimension of restricted classes of interval orders
Recommended article: Interval orders and circle orders
Recommended article: Q3329273
Recommended article: Linear-Interval Dimension and PI Orders
Recommended article: A generalization of interval orders
Recommended article: On generalized interval orders
Recommended article: Q5598296
Recommended article: Representability of interval orders
Recommended article: DIMENSION AND INTERVAL DIMENSION OF CERTAIN BIPARTITE ORDERED SETS
Recommended article: Interval orders based on arbitrary ordered sets
description: scientific article; zbMATH DE number 1420385