Ordered Sets An Introduction
This work is an introduction to the basic tools of the theory of (partially) ordered sets such as visualization via diagrams, subsets, homomorphisms, important order-theoretical constructions, and classes of ordered sets. Using a thematic approach, the author presents open or recently solved problem...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Boston, MA
Birkhäuser
2003, 2003
|
| Edition: | 1st ed. 2003 |
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- 12.3 NP problems
- 12.4 NP-completeness
- 12.5 So It’s NP-complete
- 12.6 A Polynomial Algorithm for the Fixed Point Property in Graded Ordered Sets of Bounded Width
- Exercises
- Remarks and Open Problems
- A A Primer on Algebraic Topology
- A.l Chain Complexes
- A.2 The Lefschetz Number
- A.3 (Integer) Homology
- A.4 A Homological Reduction Theorem
- Remarks and Open Problems
- B Order vs. Analysis
- B.2 Fixed Point Theorems
- B.3 An Application
- Remarks and Open Problems
- References
- 1 The Basics
- 1.1 Definition and Examples
- 1.2 The Diagram
- 1.3 Order-Preserving Mappings/Isomorphism
- 1.4 Fixed Points
- 1.5 Ordered Subsets/The Reconstruction Problem
- Exercises
- Remarks and Open Problems
- 2 Chains, Antichains and Fences
- 2.1 Chains and Zorn’s Lemma
- 2.2 Well-ordered Sets
- 2.3 A Remark on Duality
- 2.4 The Rank of an Element
- 2.5 Antichains and Dilworth’s Chain Decomposition Theorem
- 2.6 Dedekind Numbers
- 2.7 Fences and Crowns
- 2.8 Connectivity
- Exercises
- Remarks and Open Problems
- 3 Upper and Lower Bounds
- 3.1 Extremal Elements
- 3.2 Covers
- 3.3 Lowest Upper and Greatest Lower Bounds
- 3.4 Chain-Completeness and the Abian-Brown Theorem
- Exercises
- Remarks and Open Problems
- 4 Retractions
- 4.1 Definition and Examples
- 4.2 Fixed Point Theorems
- 4.3 Dismantlability
- 4.4 The Fixed Point Property for Ordered Sets of Width 2 or Height 1
- 4.5 Li and Milner’s Structure Theorem
- 4.6 Isotone Relations
- 8.3 Dedekind’s Problem for Interval Orders and Reconstruction
- 8.4 Interval Dimension
- Exercises
- Remarks and Open Problems
- 9 Lexicographic Sums
- 9.1 Definition and Examples
- 9.2 The Canonical Decomposition
- 9.3 Comparability Invariance
- 9.4 Lexicographic Sums and Reconstruction
- 9.5 An Almost Lexicographic Construction
- Exercises
- Remarks and Open Problems
- 10 Sets PQ = Hom(Q, P) and Products
- 10.1 Sets PQ = Hom(Q, P)
- 10.2 Finite Products
- 10.3 Infinite Products
- 10.4 Hashimoto’s Theorem and Automorphisms of Products
- 10.5 Arithmetic of Ordered Sets
- Exercises
- Remarks and Open Problems
- 11 Enumeration
- 11.1 Graded Ordered Sets
- 11.2 The Number of Graded Ordered Sets
- 11.3 The Asymptotic Number of Graded Ordered Sets
- 11.4 The Number of Nonisomorphic Ordered Sets
- 11.5 The Number of Automorphisms
- Exercises
- Remarks and Open Problems
- 12 Algorithmic Aspects
- 12.1 Algorithms
- 12.2 Polynomial Efficiency
- Exercises
- Remarks and Open Problems
- 5 Lattices
- 5.1 Definition and Examples
- 5.2 Fixed Point Results/The Tarski-Davis Theorem
- 5.3 Embeddings/The Dedekind-MacNeille Completion
- 5.4 Irreducible Points in Lattices
- 5.5 Finite Ordered Sets vs. Distributive Lattices
- 5.6 More on Distributive Lattices
- Exercises
- Remarks and Open Problems
- 6 Truncated Lattices
- 6.1 Definition and Examples
- 6.2 Recognizability and More
- 6.3 The Fixed Clique Property
- 6.4 Triangulations of Sn
- 6.5 Cutsets
- 6.6 Truncated Noncomplemented Lattices
- Exercises
- Remarks and Open Problems
- 7 The Dimension of Ordered Sets
- 7.1 (Linear) Extensions of Orders
- 7.2 Balancing Pairs
- 7.3 Defining the Dimension
- 7.4 Bounds on the Dimension
- 7.5 Ordered Sets of Dimension 2
- Exercises
- Remarks and Open Problems
- 8 Interval Orders
- 8.1Definition and Examples
- 8.2 The Fixed Point Property for Interval Orders