Author | Schrรถder, Bernd S. W. author |
---|---|
Title | Ordered Sets [electronic resource] : An Introduction / by Bernd S. W. Schrรถder |
Imprint | Boston, MA : Birkhรคuser Boston : Imprint: Birkhรคuser, 2003 |
Connect to | http://dx.doi.org/10.1007/978-1-4612-0053-6 |
Descript | XVII, 391 p. online resource |
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 -- 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.1 Definition and Examples -- 8.2 The Fixed Point Property for Interval Orders -- 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 -- 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