%0 Journal Article %1 TROTTER197671 %A Trotter, William T. %A Bogart, Kenneth P. %D 1976 %J Discrete Mathematics %K complexity dimension order poset %N 1 %P 71-82 %R https://doi.org/10.1016/0012-365X(76)90095-9 %T On the complexity of posets %U https://www.sciencedirect.com/science/article/pii/0012365X76900959 %V 16 %X The purpose of this paper is to discuss several invariants each of which provides a measure of the intuitive notion of complexity for a finite partially ordered set. For a poset X the invariants discussed include cardinality, width, length, breadth, dimension, weak dimension, interval dimension and semiorder dimension denoted respectively X, W(X), L(X), B(X), dim(X). Wdim(X), Idim(X) and Sdim(X). Among these invariants the following inequalities hold. B(X)⩽Idim(X)⩽Sdim(X)⩽Wdim(X)⩽dim(X)⩽W(X). We prove that every poset X with three of more points contains a partly with Idim(X) Idim(X) x,v). If M denotes the set of maximal elements and A an arbitrary anticham of X we show that Idim(X)⩽W(X-M) and Idim(X)⩽2W(X-A). We also show that there exist functions f(n,t) and (gt) such that I(X)⩽n and Idim(X)⩽tsimply dim(X)⩽f(n,t and Sdim(X)⩽t implies dim(X)⩽g(t).

@article{TROTTER197671, abstract = {The purpose of this paper is to discuss several invariants each of which provides a measure of the intuitive notion of complexity for a finite partially ordered set. For a poset X the invariants discussed include cardinality, width, length, breadth, dimension, weak dimension, interval dimension and semiorder dimension denoted respectively X, W(X), L(X), B(X), dim(X). Wdim(X), Idim(X) and Sdim(X). Among these invariants the following inequalities hold. B(X)⩽Idim(X)⩽Sdim(X)⩽Wdim(X)⩽dim(X)⩽W(X). We prove that every poset X with three of more points contains a partly with Idim(X) Idim(X) {x,v}). If M denotes the set of maximal elements and A an arbitrary anticham of X we show that Idim(X)⩽W(X-M) and Idim(X)⩽2W(X-A). We also show that there exist functions f(n,t) and (gt) such that I(X)⩽n and Idim(X)⩽tsimply dim(X)⩽f(n,t and Sdim(X)⩽t implies dim(X)⩽g(t).}, added-at = {2021-03-13T20:54:58.000+0100}, author = {Trotter, William T. and Bogart, Kenneth P.}, biburl = {https://www.bibsonomy.org/bibtex/2accea37b81c9b7e08d9089963d4f774a/tomhanika}, doi = {https://doi.org/10.1016/0012-365X(76)90095-9}, interhash = {f88a9aac9efd894d02612efddb4cca29}, intrahash = {accea37b81c9b7e08d9089963d4f774a}, issn = {0012-365X}, journal = {Discrete Mathematics}, keywords = {complexity dimension order poset}, number = 1, pages = {71-82}, timestamp = {2021-03-13T20:54:58.000+0100}, title = {On the complexity of posets}, url = {https://www.sciencedirect.com/science/article/pii/0012365X76900959}, volume = 16, year = 1976 }