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)

 
 

 

Inequalities in dimension theory for posets


Author: William T. Trotter
Journal: Proc. Amer. Math. Soc. 47 (1975), 311-316
MSC: Primary 06A10
DOI: https://doi.org/10.1090/S0002-9939-1975-0369192-2
MathSciNet review: 0369192
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The dimension of a poset $ (X,P)$, denoted $ \dim (X,P)$, is the minimum number of linear extensions of $ P$ whose intersection is $ P$. It follows from Dilworth's decomposition theorem that $ \dim (X,P) \leq \operatorname{width} (X,P)$. Hiraguchi showed that $ \dim (X,P) \leq \vert X\vert/2$. In this paper, $ A$ denotes an antichain of $ (X,P)$ and $ E$ the set of maximal elements. We then prove that $ \dim (X,P) \leq \vert X - A\vert;\dim (X,P) \leq 1 + \operatorname{width} (X - E);$ and $ \dim (X,P) \leq 1 + 2\operatorname{width} (X - A)$. We also construct examples to show that these inequalities are sharp.


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

  • [1] K. Bogart, Maximal dimensional partially ordered sets. I, Discrete Math. 5 (1973), 21-32. MR 0318013 (47:6562)
  • [2] K. Bogart and W. Trotter, Maximal dimensional partially ordered sets. II, Discrete Math. 5 (1973), 33-44. MR 0318014 (47:6563)
  • [3] R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161-166. MR 11, 309. MR 0032578 (11:309f)
  • [4] B. Dushnik and E. Miller, Partially ordered sets, Amer. J. Math. 63 (1941) 600-610. MR 3, 73. MR 0004862 (3:73a)
  • [5] T. Hiraguchi, On the dimension of orders, Sci. Rep. Kanazawa Univ. 4 (1955), 1-20. MR 17, 1045; 19, 1431. MR 0077500 (17:1045g)
  • [6] R. Kimble, Ph.D. Thesis, M.I.T., Cambridge, Mass.
  • [7] O. Ore, Theory of graphs, Amer. Math., Soc. Colloq. Publ., vol. 38, Amer. Math. Soc., Providence, R.I., 1962. MR 27 #740. MR 0150753 (27:740)
  • [8] W. T. Trotter, Dimension of the crown $ S_n^k$, Discrete Math. 8 (1974), 85-103. MR 0335376 (49:158)
  • [9] W. T. Trotter, Some families of irreducible partially ordered sets, U.S.C. Math. Tech. Rep. 06A10-2, 1974.
  • [10] -, Irreducible posets with large height exist, J. Combinatorial Theory Ser. A 17 (1974). MR 0354457 (50:6935)

Similar Articles

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

Retrieve articles in all journals with MSC: 06A10


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1975-0369192-2
Keywords: Poset, dimension, irreducible
Article copyright: © Copyright 1975 American Mathematical Society

American Mathematical Society