Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

An effective version of Dilworth's theorem


Author: Henry A. Kierstead
Journal: Trans. Amer. Math. Soc. 268 (1981), 63-77
MSC: Primary 03D45; Secondary 05A05, 06A10
MathSciNet review: 628446
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that if $ (P,\,{ < ^P})$ is a recursive partial order with finite width $ w$, then $ P$ can be covered by $ ({5^w} - 1)/4$ recursive chains. For each $ w$ we show that there is a recursive partial ordering of width $ w$ that cannot be covered by $ 4(w - 1)$ recursive chains.


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


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D45, 05A05, 06A10

Retrieve articles in all journals with MSC: 03D45, 05A05, 06A10


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1981-0628446-X
PII: S 0002-9947(1981)0628446-X
Article copyright: © Copyright 1981 American Mathematical Society