An effective version of Dilworth's theorem
Author:
Henry A. Kierstead
Journal:
Trans. Amer. Math. Soc. 268 (1981), 6377
MSC:
Primary 03D45; Secondary 05A05, 06A10
MathSciNet review:
628446
Fulltext 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.
 [B]
Dwight
R. Bean, Effective coloration, J. Symbolic Logic
41 (1976), no. 2, 469–480. MR 0416889
(54 #4952)
 [B1]
Dwight
R. Bean, Recursive Euler and Hamilton
paths, Proc. Amer. Math. Soc.
55 (1976), no. 2,
385–394. MR 0416888
(54 #4951), http://dx.doi.org/10.1090/S00029939197604168880
 [D]
R.
P. Dilworth, A decomposition theorem for partially ordered
sets, Ann. of Math. (2) 51 (1950), 161–166. MR 0032578
(11,309f)
 [J]
C. Jockush, Ramsey's theorem and recursion theory, J. Symbolic Logic 37 (1972), 268279.
 [K]
H. Kierstead, Recursive colorings of highly recursive graphs (in preparation).
 [MN]
G.
Metakides and A.
Nerode, 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
(51 #7798)
 [P]
Micha
A. Perles, A proof of Dilworth’s decomposition theorem for
partially ordered sets, Israel J. Math. 1 (1963),
105–107. MR 0168496
(29 #5758)
 [R]
Hartley
Rogers Jr., Theory of recursive functions and effective
computability, McGrawHill Book Co., New York, 1967. MR 0224462
(37 #61)
 [S]
James
H. Schmerl, Recursive colorings of graphs, Canad. J. Math.
32 (1980), no. 4, 821–830. MR 590647
(81m:03054), http://dx.doi.org/10.4153/CJM19800627
 [S1]
, The effective version of Brook's theorem (in preparation).
 [B]
 D. Bean, Effective coloration, J. Symbolic Logic 41 (1976), 469480. MR 0416889 (54:4952)
 [B1]
 , Recursive Euler and Hamilton paths, Proc. Amer. Math. Soc. 55 (1976), 385394. MR 0416888 (54:4951)
 [D]
 R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161166. MR 0032578 (11:309f)
 [J]
 C. Jockush, Ramsey's theorem and recursion theory, J. Symbolic Logic 37 (1972), 268279.
 [K]
 H. Kierstead, Recursive colorings of highly recursive graphs (in preparation).
 [MN]
 G. Metakides and A. Nerode, Recursion theory and algebra Algebra and Logic, Lecture Notes in Math., vol. 450, SpringerVerlag, Berlin and New York, 1975, pp. 209219. MR 0371580 (51:7798)
 [P]
 M. A. Perles, A proof of Dilworth's decomposition theorem for partially ordered sets, Israel J. Math. 1(1963), 105107. MR 0168496 (29:5758)
 [R]
 H. Rogers, Theory of recursive functions and effective compatability, McGrawHill, New York, 1967. MR 0224462 (37:61)
 [S]
 J. H. Schmerl, Recursive colorings of graphs, Canad. J. Math. 32 (1980), 821830. MR 590647 (81m:03054)
 [S1]
 , The effective version of Brook's theorem (in preparation).
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/S0002994719810628446X
PII:
S 00029947(1981)0628446X
Article copyright:
© Copyright 1981 American Mathematical Society
