Technical Report 285-1991

Title
On the Interplay between Interval Dimension and Dimension
Authors
Stefan Felsner, Michel Habib, and Rolf H. Möhring
Publication
SIAM Journal on Discrete Mathematics, vol. 7, 1994, pp. 32-40
Source
Download as [ps.gz]
Classification
not available
Keywords
not available
Abstract
This paper investigates a transformation P o Q between partial orders P,Q that transforms the interval dimension of P to the dimension of Q, i.e. sl Idim(P) = sl dim(Q). Such a construction has been shown before in the context of Ferrer's dimension by Cogis. Our construction can be shown to be equivalent to his, but it has the advantage of (1) being purely order-theoretic, (2) providing a geometric interpretation of interval dimension similar to that of Ore for dimension, and (3) revealing several somewhat surprising connections to other order-theoretic results. For instance, the transformation P o Q can be seen as an almost inverse of the well-known split operation, it provides a theoretical background for the influence of edge subdivision on dimension (e.g. the results of Spinrad) and interval dimension, and it turns out to be invariant with respect to changes of P that do not alter its comparability graph, thus providing also a simple new proof for the comparability invariance of interval dimension.