Book contents
- Frontmatter
- Contents
- 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 types of connected ordered sets of size at most 5
- C The numbers of ordered sets and of types of ordered sets
- D Documentation marks
- References
- List of symbols
- Index
2 - Particular classes of ordered sets
Published online by Cambridge University Press: 05 February 2012
- Frontmatter
- Contents
- 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 types of connected ordered sets of size at most 5
- C The numbers of ordered sets and of types of ordered sets
- D Documentation marks
- References
- List of symbols
- Index
Summary
This book contains results such as Dilworth's or Hiraguchi's Theorems (Chapters 4 and 6 respectively) that hold for any ordered set. However, this type of general result is rather rare. The notion of an order, although very restrictive compared to the notion of a relation, actually remains very general, a fact revealed by the huge number of different orders that can be obtained on a set with a small size (more than two million types of order on a set with 10 elements! See Appendix C). Yet in practice, the orders that naturally appear in many contexts most often belong to some particular classes of orders. These classes may be defined in many ways. They are obtained, for instance, by setting the value of a parameter (for instance, orders of dimension 2, studied in Section 6.3), by forbidding the presence of some given configurations (for instance, interval orders mentioned in Example 1.22 and in Section 2.2), by constructing the class by iteration of some given operations on a family of initial orders (for instance, series–parallel orders, defined in Section 2.2). In this chapter, we present some of the most frequent classes of orders, that will be regularly encountered all throughout the book. Although we define them in a unique way here, we will see in the exercises and later in the text that these classes often have several alternative definitions. This explains the fact that they have sometimes appeared independently in various contexts and reinforces their interest.
- Type
- Chapter
- Information
- Finite Ordered SetsConcepts, Results and Uses, pp. 42 - 66Publisher: Cambridge University PressPrint publication year: 2012