Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Large minimal realizers of a partial order

Authors: Stephen B. Maurer and I. Rabinovitch
Journal: Proc. Amer. Math. Soc. 66 (1977), 211-216
MSC: Primary 06A10
MathSciNet review: 0450144
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The size of a minimum realizer of a partial order is called the dimension of that partial order. Here we initiate the study of minimal realizers which are not minimum. As an aid to the study of such realizers, we associate to each minimal realizer certain critical digraphs. We characterize all such critical digraphs for the antichain on n elements, and consequently deduce that for $n \geqslant 4$, the maximum size of a minimal realizer is $[{n^2}/4]$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 06A10

Retrieve articles in all journals with MSC: 06A10

Additional Information

Keywords: Linear order, antichain, realizer, digraph, acyclic, unipathic, partial order
Article copyright: © Copyright 1977 American Mathematical Society