A theory of recursive dimension of ordered sets
The paper deals with countable ordered sets only. Such a set (A,\(\leq)\) is recursive iff both A and \(\leq\) are recursive sets. The recursive dimension of (A,\(\leq)\) is the least cardinal m such that (A,\(\leq)\) can be recursively embedded into \(Q^ m\) where Q is the set of rationals. The recursive chain covering number of (A,\(\leq)\) is the minimal number of disjoint recursive chains the union of which is A. The authors prove many assertions showing relations between these concepts. Typical examples: There is a recursive ordered set of width 3 and recursive chain covering number 4 which has no finite recursive dimension (Theorem 0). Every recursive ordered set of width not more than 2 has recursive dimension not more than 5 (Theorem 2). For the proofs they have used a nontraditional game theoretical approach.
- A bound on the dimension of interval orders
- A decomposition theorem for partially ordered sets
- An Effective Version of Dilworth's Theorem
- An Effective Version of Hall's Theorem
- Effective coloration
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 3809541 (Why is no real title available?)
- scientific article; zbMATH DE number 3769624 (Why is no real title available?)
- scientific article; zbMATH DE number 3771663 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Partial orderings of fixed finite dimension: Model companions and density
- Partially Ordered Sets
- Recursive Euler and Hamilton Paths
- Two-dimensional partial orderings: Recursive model theory
- Fundamentals of planar ordered sets
- On the dimensions of ordered sets of bounded degree
- An on-line graph coloring algorithm with sublinear performance ratio
- On the strength of König's duality theorem for infinite bipartite graphs
- On-line chain partitions of orders
- Order relations of measures when avoiding decreasing sets.
- On-line version of Rabinovitch theorem for proper intervals
- On-line dimension for posets excluding two long incomparable chains
- The graph of critical pairs of a crown
- On-line dimension of semi-orders
- A subexponential upper bound for the on-line chain partitioning problem
- Theory of Dimension for Large Discrete Sets and Applications
- Minors and dimension
- scientific article; zbMATH DE number 4079488 (Why is no real title available?)
- scientific article; zbMATH DE number 39526 (Why is no real title available?)
- scientific article; zbMATH DE number 53952 (Why is no real title available?)
- scientific article; zbMATH DE number 3993569 (Why is no real title available?)
- A generalization of the Keisler‐Morley theorem to recursively saturated ordered structures
- Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
- Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
- On the theory of the PTIME degrees of the recursive sets
- On-line chain partitions of orders: a survey
- The strong selection property and ordered sets of finite length
This page was built for publication: A theory of recursive dimension of ordered sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2266723)
