1994/02/01 by Stefan Felsner, Michel Habib, Rolf H. Möhring · 1 citation
Computer Science · Mathematics · #Numerical Methods and Algorithms #semigroups and automata theory #Mathematical and Theoretical Analysis #Mathematics #Dimension (graph theory) #Effective dimension #Combinatorics #Dimension function #Invariant (physics) #Inductive dimension #Interval (graph theory) #Comparability #Discrete mathematics #Hausdorff dimension #Packing dimension #Minkowski–Bouligand dimension #Simple (philosophy) #Mathematical analysis
paper · doi:10.1137/s089548019121885x
openalex publication_date 1994/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/26
This paper investigates a transformation P → Q between partial orders P,Q that transforms the interval dimension of P to the dimension of Q, i.e., idim ( P ) = dim ( Q ). Such a construction has been shown before in the context of Ferrer’s dimension by Cogis [Discrete Math., 38 (1982), pp. 47–52]. The construction in this paper 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 [Amer. Math. Soc. Colloq. Publ., Vol. 38, 1962] for dimension, and (3) revealing several somewhat surprising connections to other order-theoretic results. For instance, the transformation P → Q can be seen as almost an 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 [Order, 5 (1989), pp. 143–147]) and interval dimension, and it turns out to be invariant with respect to changes of P that do not alter its comparability graph, thus also providing a simple new proof for the comparability invariance of interval dimension.