A theory of recursive dimension for ordered sets |
| |
Authors: | Henry A Kierstead George F McNulty William T Trotter Jr |
| |
Institution: | (1) Department of Mathematics, and Statistics, University of South Carolina, 29208 Columbia, SC, USA |
| |
Abstract: | 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.This paper was prepared while the authors were supported, in part, by NSF grant ISP-80-11451. In addition, the second author received support under NSF grant MCS-80-01778 and the third author received support under NSF grant MCS-82-02172. |
| |
Keywords: | Primary: 06A10 secondary: 05C35 03D20 |
本文献已被 SpringerLink 等数据库收录! |
|