Technical Report 207-1988
- Title
- Interval Dimension is a Comparability Invariant.
- Authors
- Michel Habib, David Kelly, and Rolf H. Möhring
- Publication
- Discrete Mathematics, vol. 88, 1991, pp. 211-229
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
We allow orders (ordered sets) to be infinite. An interval order is an order that does not contain 2+2 as an induced suborder. The interval dimension of an order is the minimum number of interval orders (on the same set) whose intersection is the given order. We show that orders with the same comparability graph have the same interval dimension, answering a question raised by Dagan, Golumbic and Pinter for finite orders. We also obtain the analogous result for some other notions of dimension.