Finite Ordered Sets: Concepts, Results and Uses (Encyclopedia of Mathematics and its Applications, Series Number 144)

"Ordered sets are ubiquitous in mathematics and have significant applications in computer science, statistics, biology and the social sciences. As the first book to deal exclusively with finite ordered sets, this book will be welcomed by graduate students and researchers in all of these areas. Beginning with definitions of key concepts and fundamental results (Dilworth's and Sperner's theorem, interval and semiorders, Galois connection, duality with distributive lattices, coding and dimension theory), the authors then present applications of these structures in fields such as preference modelling and aggregation, operational research and management, cluster and concept analysis, and data mining. Exercises are included at the end of each chapter with helpful hints provided for some of the most difficult examples. The authors also point to further topics of ongoing research"-- Provided by publisher 5.1 Distributive lattices5.2 The distributive lattice associated with an ordered set; 5.3 Representations of a distributive lattice; 5.4 Dualities: preorders-topologies, orders-distributive lattices; 5.5 Duality between orders and spindles of linear orders; 5.6 Further topics and references; 5.7 Exercises; 6 Order codings and dimensions; 6.1 Boolean codings and Boolean dimension of an ordered set; 6.2 Dimension of an ordered set; 6.3 2-dimensional ordered sets; 6.4 k-dimension of an ordered set; 6.5 Further topics and references; 6.6 Exercises; 7 Some uses; 7.1 Models of preferences 3.2 Join- and meet-generating sets3.3 Closure and dual closure operators; 3.4 Residuated, residual, and Galois maps; 3.5 The Galois connection associated with a binary relation; 3.5.1 Galois lattice; 3.5.2 Table of an ordered set; 3.5.3 Completion of an ordered set; 3.6 Further topics and references; 3.7 Exercises; 4 Chains and antichains; 4.1 Dilworth's decomposition theorem; 4.2 Matchings and transversals in a bipartite ordered set; 4.3 The Sperner property; 4.4 Direct products of chains; 4.5 Further topics and references; 4.6 Exercises; 5 Ordered sets and distributive lattices Cover; Half-title; Title; Copyright; Contents; Preface; 1 Concepts and examples; 1.1 Ordered sets; 1.1.1 Orders and strict orders; 1.1.2 Graphs associated with an ordered set; 1.1.3 Diagram of an ordered set; 1.1.4 Isomorphism and duality; 1.2 Examples of uses; 1.2.1 Mathematics; 1.2.2 Biology; 1.2.3 Computer science; 1.2.4 Social sciences; 1.2.5 Operations research; 1.3 Ordered subsets and extensions; 1.3.1 Ordered subsets; 1.3.2 Chains, antichains, and associated parameters; 1.3.3 Extensions; 1.4 Particular elements and subsets; 1.4.1 Meets, joins, and irreducible elements 1.4.2 Downsets and upsets (ideals and filters)1.5 Constructing ordered sets from given ones; 1.5.1 Substitution, disjoint union, linear sum, lexicographic product; 1.5.2 Direct product; 1.6 Further topics and references; 1.7 Exercises; 2 Particular classes of ordered sets; 2.1 Ranked, semimodular, and bipartite ordered sets; 2.2 Ordered sets with forbidden configurations; 2.3 Semilattices and lattices; 2.4 Linearly ordered sets and tournaments; 2.5 Further topics and references; 2.6 Exercises; 3 Morphisms of ordered sets; 3.1 Isotone and antitone maps: exponentiation 7.2 Preference aggregation: Arrowian theorems for orders7.3 The roles of orders in cluster analysis; 7.4 Implicational systems, Moore families and Galois data analysis; 7.5 Orders in scheduling; 7.5.1 The single-machine scheduling problem; 7.5.2 The m-machine scheduling problem; 7.5.3 The two-step (and two-machine) scheduling problem; 7.6 Further topics and references; 7.6.1 Preference models; 7.6.2 Preference aggregation: Arrowian theorems for orders; 7.6.3 The roles of orders in cluster analysis; 7.6.4 Implicational systems, Moore families, and Galois data analysis Machine generated contents note: Preface; 1. Concepts and examples; 2. Particular classes of ordered sets; 3. Morphisms of ordered sets; 4. Chains and antichains; 5. Ordered sets and distributive lattices; 6. Order codings and dimensions; 7. Some uses; A. About algorithmic complexity; B. The 58 non-isomorphic connected ordered sets with at most 5 elements; C. The numbers of ordered sets and of non-isomorphic ordered sets; D. Documentation marks; List of symbols; Bibliography; Index. A comprehensive account that gives equal attention to the combinatorial, logical and applied aspects of partially ordered sets