An Effective Version of Dilworth's Theorem

DOI10.2307/1998337zbMath0485.03019OpenAlexW4235299149MaRDI QIDQ3944587

Henry A. Kierstead

Publication date: 1981

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/1998337

zbMATH Keywords

recursive chainsrecursive partial order with finite width

Mathematics Subject Classification ID

Theory of numerations, effectively presented structures (03D45)

Related Items

A subexponential upper bound for the on-line chain partitioning problem, On-line scheduling of jobs with fixed start and end times, On-line dimension of semi-orders, On-line algorithms for ordered sets and comparability graphs, Coloring interval graphs with First-Fit, Asymmetric coloring games on incomparability graphs, On-line chain partitioning of up-growing interval orders, An on-line graph coloring algorithm with sublinear performance ratio, On-line algorithms for orders, On-line chain partitions of orders, Graphs are not universal for online computability, Primitive recursive reverse mathematics, Improved lower bound on the on-line chain partitioning of semi-orders with representation, Improved lower bounds on the on-line chain partitioning of posets of bounded dimension, Variations of statement, variations of strength. The case of the Rival-Sands theorems, A structure of punctual dimension two, On-line dimension for posets excluding two long incomparable chains, On-line chain partitions of up-growing semi-orders, (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE, A structure theory for ordered sets, Online presentations of finitely generated structures, Lower bounds for randomized algorithms for online chain partitioning, Binary subtrees with few labeled paths, On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains, On the strength of König's duality theorem for infinite bipartite graphs, The online graph bandwidth problem, An easy subexponential bound for online chain partitioning, First-fit coloring of bounded tolerance graphs, Unnamed Item, A theory of recursive dimension of ordered sets, Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes, Punctual definability on structures, FOUNDATIONS OF ONLINE STRUCTURE THEORY, On-line chain partitions of orders: a survey, On the complexity of finding the chromatic number of a recursive graph. I: The bounded case, Unnamed Item