An effective version of Dilworth’s theorem

Kierstead, Henry A.

doi:10.1090/S0002-9947-1981-0628446-X

An effective version of Dilworth’s theorem
HTML articles powered by AMS MathViewer

by Henry A. Kierstead

Trans. Amer. Math. Soc. 268 (1981), 63-77

DOI: https://doi.org/10.1090/S0002-9947-1981-0628446-X

PDF | Request permission

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

Dwight R. Bean, Effective coloration, J. Symbolic Logic 41 (1976), no. 2, 469–480. MR 416889, DOI 10.2307/2272247
Dwight R. Bean, Recursive Euler and Hamilton paths, Proc. Amer. Math. Soc. 55 (1976), no. 2, 385–394. MR 416888, DOI 10.1090/S0002-9939-1976-0416888-0
R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166. MR 32578, DOI 10.2307/1969503

Ramsey’s theorem and recursion theory

37

Recursive colorings of highly recursive graphs

G. Metakides and A. Nerode, Recursion theory and algebra, Algebra and logic (Fourteenth Summer Res. Inst., Austral. Math. Soc., Monash Univ., Clayton, 1974) Lecture Notes in Math., Vol. 450, Springer, Berlin, 1975, pp. 209–219. MR 0371580
Micha A. Perles, A proof of Dilworth’s decomposition theorem for partially ordered sets, Israel J. Math. 1 (1963), 105–107. MR 168496, DOI 10.1007/BF02759805
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto-London, 1967. MR 0224462
James H. Schmerl, Recursive colorings of graphs, Canadian J. Math. 32 (1980), no. 4, 821–830. MR 590647, DOI 10.4153/CJM-1980-062-7

The effective version of Brook’s theorem