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 is a recursive partial order with finite width , then can be covered by recursive chains. For each we show that there is a recursive partial ordering of width that cannot be covered by recursive chains.

**[**Dwight R. Bean,**B**]*Effective coloration*, J. Symbolic Logic**41**(1976), no. 2, 469–480. MR**0416889****[**Dwight R. Bean,**B1**]*Recursive Euler and Hamilton paths*, Proc. Amer. Math. Soc.**55**(1976), no. 2, 385–394. MR**0416888**, 10.1090/S0002-9939-1976-0416888-0**[**R. P. Dilworth,**D**]*A decomposition theorem for partially ordered sets*, Ann. of Math. (2)**51**(1950), 161–166. MR**0032578****[**C. Jockush,**J**]*Ramsey's theorem and recursion theory*, J. Symbolic Logic**37**(1972), 268-279.**[**H. Kierstead,**K**]*Recursive colorings of highly recursive graphs*(in preparation).**[**G. Metakides and A. Nerode,**MN**]*Recursion theory and algebra*, Algebra and logic (Fourteenth Summer Res. Inst., Austral. Math. Soc., Monash Univ., Clayton, 1974) Springer, Berlin, 1975, pp. 209–219. Lecture Notes in Math., Vol. 450. MR**0371580****[**Micha A. Perles,**P**]*A proof of Dilworth’s decomposition theorem for partially ordered sets*, Israel J. Math.**1**(1963), 105–107. MR**0168496****[**Hartley Rogers Jr.,**R**]*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[**James H. Schmerl,**S**]*Recursive colorings of graphs*, Canad. J. Math.**32**(1980), no. 4, 821–830. MR**590647**, 10.4153/CJM-1980-062-7**[**-,**S1**]*The effective version of Brook's theorem*(in preparation).

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:
https://doi.org/10.1090/S0002-9947-1981-0628446-X

Article copyright:
© Copyright 1981
American Mathematical Society