Ordered Sets

An introduction to the basic tools of the theory of (partially) ordered sets such as visualization via diagrams, subsets, and homomorphisms. Using a thematic approach, the author presents open or recently solved problems to motivate the development of constructions and investigations for new classes of ordered sets. The text can be used as a focused follow-up or companion to a first proof (set theory and relations) or graph theory course. Rich in exercises, the book will be a valuable text for undergraduate/graduate students and an excellent resource for interested researchers.

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.1Definition 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.