A theory of recursive dimension for ordered sets

Henry A. Kierstead, George F. McNulty, William T. Trotter

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


The classical theorem of R. P. Dilworth asserts that a partially ordered set of width n can be partitioned into n chains. Dilworth's theorem plays a central role in the dimension theory of partially ordered sets since chain partitions can be used to provide embeddings of partially ordered sets in the Cartesian product of chains. In particular, the dimension of a partially-ordered set never exceeds its width. In this paper, we consider analogous problems in the setting of recursive combinatorics where it is required that the partially ordered set and any associated partition or embedding be described by recursive functions. We establish several theorems providing upper bounds on the recursive dimension of a partially ordered set in terms of its width. The proofs are highly combinatorial in nature and involve a detailed analysis of a 2-person game in which one person builds a partially ordered set one point at a time and the other builds the partition or embedding.

Original languageEnglish (US)
Pages (from-to)67-82
Number of pages16
Issue number1
StatePublished - Mar 1 1984
Externally publishedYes


  • AMS (MOS) subject classifications (1980): Primary: 06A10, secondary: 05C35, 03D20
  • Partially ordered sets
  • dimension
  • recursive combinatorics
  • recursive function

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics


Dive into the research topics of 'A theory of recursive dimension for ordered sets'. Together they form a unique fingerprint.

Cite this