Structures of Partial Orders
While visualizing a poset (X, IB) with a Hasse diagram, it is initially interesting to observe the following:
- PDF / 949,591 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 194 Views
Structures of Partial Orders
5.1 Motivation While visualizing a poset (X, IB) with a Hasse diagram, it is initially interesting to observe the following: 1. Whether or not there is a messy system of lines. 2. Whether the Hasse diagram resembles a a. triangular shape or b. rectangular shape. 3. Whether there are different components or approximate components. As (X, IB) is based on a data matrix, we want to relate these three aspects in the Hasse diagram with the properties of the data matrix. That is, we want to discover properties of the data matrix through the structure of Hasse diagrams. Therefore, Chapter 5 is organized as follows: (1) we revisit the concept of levels, (2) we show how down sets and up sets are related to attribute properties, (3) the concept of separation of object subsets is introduced, (4) we explain why and how far structures of a poset and properties of a data matrix are related. Finally, (5) the concept of dominance of object subsets is discussed.
5.2 Levels and Shapes of a Hasse Diagram 5.2.1 Width and Height In Chapter 2, height and width of a poset have been introduced. Both numbers describe the shape of a Hasse diagram by inscribing it into a rectangle with height and width. The determination of width may be difficult (at least in complex Hasse diagrams) as the following example (Fig. 5.1) shows. In Fig. 5.1, the height is 3, and following the drawing protocol of Hasse diagrams (by different software packages like WHASSE and PyHasse, see Chapter 17) we
R. Brüggemann, G.P. Patil, Ranking and Prioritization for Multi-indicator Systems, Environmental and Ecological Statistics 5, DOI 10.1007/978-1-4419-8477-7_5, C Springer Science+Business Media, LLC 2011
57
58
5 Structures of Partial Orders
Fig. 5.1 Width and antichains
d
b
e
c
a
identify the antichains {b, c}, {d, e} both having two elements. However, the width of the poset in Fig. 5.1 is 3, because the maximum antichain is {b, c, e}. In messy Hasse diagrams, it is difficult to identify the maximum antichain by visual inspection. Therefore, we use the concept of levels as a visual proxy for the discussion of shapes of the Hasse diagrams.
5.2.2 Level The concept of levels is very useful: • Due to the level concept, a weak order can be found among the objects. • Levels are descriptive tools as they allow a partitioning of the objects even in messy Hasse diagrams. • Levels are the starting point for a visualization technique, developed by Myers and Patil (2008), suitable for a huge number of objects. 5.2.2.1 Construction Let MAX ⊆ X be the set of maximal elements of a poset (see Chapter 2). (5.1) lg = number of cover relations in the maximum of all maximal chains.
(5.2)
An element x ∈ MAX gets the level number lev(x) = lg + 1 = height.
(5.3)
Now perform a partitioning of X as follows. Eliminate MAX from X and determine the new MAX. This new set gets a level number reduced by 1. Continue the elimination process until X is exhausted. The level sets are the equivalence classes under the equivalence relation: lev = lev(x) =
Data Loading...
