222
M. Fattore and A. Arcagni
2.2 Matrix Representations of Posets
The simplest way to represent algebraically finite partial order relations is by means
of the n × n incidence matrix Z, defined as Z ij = 1 if x i π x j and Z ij = 0
otherwise. Alternatively, one can define the n × n cover matrix G, whose entries are
given by G ij = 1 if x i ≺ π x j and G ij = 0 otherwise. Since the cover relation and
the partial order relation determine each other, matrices Z and G can be obtained
one from the other, by simple algebraic formulas (Patil and Taillie 2004). Matrices
Z and G are extremely useful in practical computations and provide easy ways to
inspect and investigate relevant features of the underlying poset.
2.3 Graphical Representation of Posets
When the number of elements is small enough, posets can be depicted graphically,
in various ways (Neggers and Kim 1998). The most useful and widely adopted
one is by means of Hasse diagrams, which are directed acyclic graphs, reproducing
the cover relation. In a Hasse diagram, poset elements are represented by vertices,
or nodes; if x i π x j , then node corresponding to x j is placed higher than node
corresponding to x i and, if x i ≺ π x j , an edge is inserted between them. By
transitivity, one can then recover all of the comparabilities of the input poset. Many
examples of Hasse diagrams will be shown in the rest of the chapter (and across the
entire book).
2.4 Linear Extensions
Given two partially ordered sets π = (X, π ) and σ = (X, σ ) on the same set
X, we say that σ is an extension of π , if it is obtained from the latter by turning
some incomparabilities into comparabilities, i.e. if x i π x j in π implies x i σ x j
in σ . If σ is an extension of π and also a linear order, then it is called a linear
extension of π . The linear extensions of π are all the possible orderings of elements
of π which are compatible with the partial order relation π , i.e. that do not switch
or eliminate any comparability of π . A simple, but fundamental, theorem in partial
order theory states that any finite poset π is uniquely identified by the set
of its linear extensions. As discussed later in the chapter, this is a key property for
applications of poset theory to data analysis.
M. Fattore and A. Arcagni
2.2 Matrix Representations of Posets
The simplest way to represent algebraically finite partial order relations is by means
of the n × n incidence matrix Z, defined as Z ij = 1 if x i π x j and Z ij = 0
otherwise. Alternatively, one can define the n × n cover matrix G, whose entries are
given by G ij = 1 if x i ≺ π x j and G ij = 0 otherwise. Since the cover relation and
the partial order relation determine each other, matrices Z and G can be obtained
one from the other, by simple algebraic formulas (Patil and Taillie 2004). Matrices
Z and G are extremely useful in practical computations and provide easy ways to
inspect and investigate relevant features of the underlying poset.
2.3 Graphical Representation of Posets
When the number of elements is small enough, posets can be depicted graphically,
in various ways (Neggers and Kim 1998). The most useful and widely adopted
one is by means of Hasse diagrams, which are directed acyclic graphs, reproducing
the cover relation. In a Hasse diagram, poset elements are represented by vertices,
or nodes; if x i π x j , then node corresponding to x j is placed higher than node
corresponding to x i and, if x i ≺ π x j , an edge is inserted between them. By
transitivity, one can then recover all of the comparabilities of the input poset. Many
examples of Hasse diagrams will be shown in the rest of the chapter (and across the
entire book).
2.4 Linear Extensions
Given two partially ordered sets π = (X, π ) and σ = (X, σ ) on the same set
X, we say that σ is an extension of π , if it is obtained from the latter by turning
some incomparabilities into comparabilities, i.e. if x i π x j in π implies x i σ x j
in σ . If σ is an extension of π and also a linear order, then it is called a linear
extension of π . The linear extensions of π are all the possible orderings of elements
of π which are compatible with the partial order relation π , i.e. that do not switch
or eliminate any comparability of π . A simple, but fundamental, theorem in partial
order theory states that any finite poset π is uniquely identified by the set
of its linear extensions. As discussed later in the chapter, this is a key property for
applications of poset theory to data analysis.