6.1: Basic Notation and Terminology

A partially ordered set or poset \(P\) is a pair \((X,P)\) where \(X\) is a set and \(P\) is a reflexive, antisymmetric, and transitive binary relation on \(X\). (Refer to Section B.10 for a refresher of what these properties are if you need to.) We call \(X\) the ground set while \(P\) is a partial order on \(X\). Elements of the ground set \(X\) are also called points, and the poset \(P\) is finite if its ground set \(X\) is a finite set.

Example 6.3

Let \(X=\{a,b,c,d,e,f\}\). Consider the following binary relations on \(X\).

\(R_1=\{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(a,b),(a,c),(e,f)\}\)

\(R_2=\{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(d,b),(d,e),(b,a),(e,a),(d,a),(c,f)\}\)

\(R_3=\{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(a,c),(a,e),(a,f),(b,c),(b,d),(b,e),(b,f),(d,e),(d,f),(e,f)\}\)

\(R_4=\{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(d,b),(b,a),(e,a),(c,f)\}\)

\(R_5=\{(a,a),(c,c),(d,d),(e,e),(a,e),(c,a),(c,e),(d,e)\}\)

\(R_6=\{(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(d,f),(b,e),(c,a),(e,b)\}\)

Which of the binary relations are partial orders on \(X\)? For those that are not partial orders on \(X\), which property or properties are violated?

Solution

A bit of checking confirms that \(R_1, R_2\) and \(R_3\) are partial orders on \(X\), so \(P_1=(X,R_1), P_2=(X,R_2)\) and \(P_3=(X,R_3)\) are posets. Several of the other examples we will discuss in this chapter will use the poset \(P_3=(X,R_3)\).

On the other hand, \(R_4, R_5\) and \(R_6\) are not partial orders on \(X\). Note that \(R_4\) is not transitive, as it contains (\(d,b\)) and (\(b,a\)) but not \((d,a)\). The relation \(R_5\) is not reflexive, since it doesn't contain \((b,b)\). (Also, it also doesn't contain \((f,f)\), but one shortcoming is enough.) Note that \(R_5\) is a partial order on \(\{a,b,d,e\}\). The relation \(R_6\) is not antisymmetric, as it contains both \((b,e)\) and \((e,b)\).

When \(P=(X,P)\) is a poset, it is common to write \(x \leq y\) in \(P\) or \(y \geq x\) in \(P\) as substitutes for \((x,y) \in P\). Of course, the notations \(x<y\) in \(P\) and \(y>x\) in \(P\) mean \(x \leq y\) in \(P\) and \(x \neq y\). When the poset \(P\) remains fixed throughout a discussion, we will sometimes abbreviate \(x \leq y\) in \(P\) by just writing \(x \leq y\), etc. When \(x\) and \(y\) are distinct points from \(X\), we say \(x\) is covered by \(y\) in \(P\) when \(x<y\) in \(P\), and there is no point \(z \in X\) for which \(x<z\) and \(z<y\) in \(P\). For example, in the poset \(P_3=(X,R_3)\) from Example 6.3, \(d\) is covered by \(e\) and \(c\) covers \(b\). However, \(a\) is not covered by \(f\), since \(a<e<f\) in \(R_3\). We can then associate with the poset \(P\) a cover graph \(G\) whose vertex set is the ground set \(X\) of \(P\) with \(xy\) an edge in \(G\) if and only if one of \(x\) and \(y\) covers the other in \(P\). Again, for the poset \(P_3\) from Example 6.3, we show the cover graph on the left side of Figure 6.4. Actually, on the right side of this figure is just another drawing of this same graph.

Figure 6.4. Cover Graph

It is convenient to illustrate a poset with a suitably drawn diagram of the cover graph in the Euclidean plane. We choose a standard horizontal/vertical coordinate system in the plane and require that the vertical coordinate of the point corresponding to \(y\) be larger than the vertical coordinate of the point corresponding to \(x\) whenever \(y\) covers \(x\) in \(P\). Each edge in the cover graph is represented by a straight line segment which contains no point corresponding to any element in the poset other than those associated with its two end points. Such diagrams are called Hasse diagrams (poset diagrams, order diagrams, or just diagrams). Now it should be clear that the drawing on the right side of Figure 6.4 is a diagram of the poset \(P_3\) from Example 6.3, while the diagram on the left is not.

For posets of moderate size, diagrams are frequently used to define a poset—rather than the explicit binary relation notation illustrated in Example 6.3. In Figure 6.5, we illustrate a poset \(P=(X,P)\) with ground set \(X=[17]=\{1,2,…,17\}\). It would take several lines of text to write out the binary relation \(P\), and somehow the diagram serves to give us a more tactile sense of the properties of the poset.

Figure 6.5. A Poset on 17 Points

Discussion 6.6.

Alice and Bob are talking about how you communicate with a computer in working with posets. Bob says that computers have incredible graphics capabilities these days and that you just give the computer a pdf scan of a diagram. Alice says that she doubts that anybody really does that. Carlos says that there are several effective strategies. One way is to label the points with positive integers from \([n]\) where \(n\) is the number of points in the ground set and then define a 0–1 \(n \times n\) matrix A with entry \(a(i,j)=1\) when \(i \leq j\) in \(P\) and \(a(i,j)=0\) otherwise. Alternatively, you can just provide for each element \(i\) in the ground set a vector \(U(x)\) listing all elements which are greater than \(x\) in \(P\). This vector can be what computer scientists call a linked list.

A partial order \(P\) is called a total order (also, a linear order) if for all \(x,y \in X\), either \(x \leq y\) in \(P\) or \(y \leq x\) in \(P\). For small finite sets, we can specify a linear order by listing the elements from least to greatest. For example, \(L=[b,c,d,a,f,g,e]\) is the linear order on the ground set \(\{a,b,c,d,e,f,g\}\) with \(b<c<d<a<f<g<e\) in \(L\).

The set of real numbers comes equipped with a natural total order. For example, \(1<7/5<\sqrt{2}< \pi \) in this order. But in this chapter, we will be interested primarily with partial orders that are not linear orders. Also, we note that special care must be taken when discussing partial orders on ground sets whose elements are real numbers. For the poset shown in Figure 6.5, note that 14 is less than 8, while 3 and 6 are incomparable. Best not to tell your parents that you've learned that under certain circumstances, 14 can be less than 8 and that you may be able to say which of 3 and 6 is larger than the other. The subtlety may be lost in the heated discussion certain to follow.

Example 6.7

There are several quite natural ways to construct posets.

1. A family \(\mathcal{F}\) of sets is partially ordered by inclusion, i.e., set \(A \leq B\) if and only if \(A\) is a subset of \(B\).
2. A set \(X\) of positive integers is partially ordered by division—without remainder, i.e., set \(m \leq n\) if and only if \(n \equiv 0\) (mod \(m\)).
3. A set \(X\) of \(t\)-tuples of real numbers is partially ordered by the rule

   \((a_1,a_2,…,a_t) \leq (b_1,b_2,…,b_t)\)

   if and only if \(a_i \leq b_i\) in the natural order on \(\mathcal{R}\) for \(i = 1,2,...,t\).

4. When \(L_1, L_2,…,L_k\) are linear orders on the same set \(X\), we can define a partial order \(P\) on \(X\) by setting \(x \leq y\) in \(P\) if and only if \(x \leq y\) in \(L_i\) for all \(i=1,2,…,k\).

We illustrate the first three constructions with the posets shown in Figure 6.8. As is now clear, in the discussion at the very beginning of this chapter, Dave drew a diagram for the poset determined by the intersection of the linear orders given by Alice and the movie critic.

Figure 6.8. Constructing Posets

Distinct points \(x\) and \(y\) in a poset \(P=(X,P)\) are comparable if either \(x<y\) in \(P\) or \(x>y\) in \(P\); otherwise \(x\) and \(y\) are incomparable. If \(x\) and \(y\) are incomparable in \(P\), we sometimes write \(x‖y\) in \(P\).With a poset \(P=(X,P)\), we associate a comparability graph \(G_1=(X,E_1)\) and an incomparability graph \(G_2=(X,E_2)\). The edges in the comparability graph \(G_1\) consist of the comparable pairs and the edges in the incomparability graph are the incomparable pairs. We illustrate these definitions in Figure 6.9 where we show the comparability graph and the incomparability graph of the poset \(P_3\).

Figure 6.9. Comparability and Incomparability Graphs

When \(P=(X,P)\) is a poset and \(Y \subseteq X\), the binary relation \(Q=P \bigcap (Y \times Y)\) is a partial order on \(Y\), and we call the poset \((Y,Q)\) a subposet of \(P\). In Figure 6.10, we show a subposet of the poset first presented in Figure 6.5.

Figure 6.10. A Subposet

When \(P=(X,P)\) is a poset and \(C\) is a subset of \(X\), we say that \(C\) is a chain if every distinct pair of points from \(C\) is comparable in \(P\). When \(P\) is a linear order, the entire ground set \(X\) is a chain. Dually, if \(A\) is a subset of \(X\), we say that \(A\) is an antichain if every distinct pair of points from \(A\) is incomparable in \(P\). Note that a one-element subset is both a chain and an antichain. Also, we consider the empty set as both a chain and an antichain.

The height of a poset \(P=(X,P)\), denoted height⁡(P), is the largest \(h\) for which there exists a chain of \(h\) points in \(P\). Dually, the width of a poset \(P=(X,P)\), denoted width⁡(P), is the largest \(w\) for which there exists an antichain of \(w\) points in \(P\).

Discussion 6.11

Given a poset \(P=(X,P)\), how hard is to determine its height and width? Bob says that it is very easy. For example, to find the width of a poset, just list all the subsets of \(X\). Delete those which are not antichains. The answer is the size of the largest subset that remains. He is quick to assert that the same approach will work to find the height. Alice groans at Bob's naivety and suggests that he should read further in this chapter.