Interval dimension and MacNeille completion. (English) Zbl 0796.06007
Summary: Equality between the interval dimensions of a poset and its MacNeille completion, announced by the authors in C. R. Acad. Sci., Paris, Sér. I 313, No. 13, 893-898 (1991; Zbl 0734.06003), has been obtained by the authors as a byproduct of their study of Galois lattices [“Incidence structures, coding and lattice of maximal antichains”, RR92, LIRMM, Montpellier (1992), submitted to Discr. Math.]. The purpose of this note is to give a direct proof, similar to the classical proof of Baker’s result stating that the dimension (in the Dushnik-Miller sense) of a poset and its MacNeille completion are the same.
Keywords:
coding; antichains; interval orders; Ferrers relations; interval dimension; MacNeille completion; Galois latticesCitations:
Zbl 0734.06003References:
| [1] | K. A. Baker (1961) Dimension, join-independence, and breadth in partially ordered sets, unpublished. |
| [2] | R. Bonnet and M. Pouzet (1969) Extensions et stratifications d’ensembles dispers?s,C.R. Acad. Sci. 268 S?rie A, 1512-1515. · Zbl 0188.04203 |
| [3] | O. Cogis (1980) Dimension Ferrers des graphes orient?s, Th?se de Doctorat d’Etat, Universit? P. et M. Curie, Paris 1980; also inDiscrete Mathematics 38 (1982), 33-46. |
| [4] | O. Cogis (1982) On the Ferrers dimension of digraph,Discrete Mathematics 38, 47-52. · Zbl 0472.06007 · doi:10.1016/0012-365X(82)90167-4 |
| [5] | B. Dushnik and E. W. Miller (1941) Partially ordered sets,Amer. J. Math. 63, 600-610. · Zbl 0025.31002 · doi:10.2307/2371374 |
| [6] | P. C. Fishburn (1985)Interval Orders and Interval Graphs, Wiley. · Zbl 0568.05047 |
| [7] | M. Habib, M. Morvan, M. Pouzet, and J. X. Rampon (1991) Extensions intervallaires minimales,C.R. Acad. Sci. Paris 232,313,s?rie I, 893-898. · Zbl 0734.06003 |
| [8] | M. Habib, M. Morvan, M. Pouzet, and J. X. Rampon (1992) Incidence structures, coding and lattice of maximal antichains, RR 92, LIRMM, Montpellier, submitted toDiscrete Mathematics. |
| [9] | T. Hiraguchi (1951) On the dimension of partially ordered sets,Sci. Rep. Kanazawa Univ. 4, 77-94. · Zbl 0200.00013 |
| [10] | D. Kelly and W. T. Trotter, (1982) Dimension theory for ordered sets, in I. Rival (ed.),Ordered Sets, D. Reidel Publishing Company, 171-211. · Zbl 0499.06003 |
| [11] | H. M. MacNeille (1937) Partially ordered sets,Trans. Amer. Soc. 42, 416-460. · Zbl 0017.33904 · doi:10.1090/S0002-9947-1937-1501929-X |
| [12] | E. C. Milner and M. Pouzet (1990) Note on the dimension of an ordered set,Order 7, 101-102. · Zbl 0792.06003 · doi:10.1007/BF00383178 |
| [13] | J. Mitas (1992) Interval orders based on arbitrary ordered sets, preprint no 1466, Fachbereich Mathematik, TH Darmstadt, April 1992. |
| [14] | O. Ore (1962)Theory of Graphs, Colloquium Publication 38, Amer. Math. Soc., Providence, R.I. · Zbl 0105.35401 |
| [15] | W. T. Trotter and K. P. Bogart (1976) Maximal dimensional partially ordered sets III: a characterization of Hiraguchi’s inequality for interval dimension,Discrete Math. 15, 389-400. · Zbl 0336.06004 · doi:10.1016/0012-365X(76)90052-2 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
