Skip to main content
Logo image

Applied Combinatorics

Section 6.2 Additional Concepts for Posets

We say \((X,P)\) and \((Y,Q)\) are isomorphic, and write \((X,P) \cong(Y,Q)\) if there exists a bijection (1–1 and onto map) \(f:X\to Y\) so that \(x_1\le x_2\) in \(P\) if and only if \(f(x_1)\le f(x_2)\) in \(Q\text{.}\) In this definition, the map \(f\) is called an isomorphism from \(\bfP\) to \(\bfQ\text{.}\) In Figure 6.8, the first two posets are isomorphic.

Discussion 6.12.

Bob sees a pattern linking the first two posets shown in Figure 6.8 and asserts that any poset of one of these two types is isomorphic to a poset of the other type. Alice admits that Bob is right—but even more is true. The four constructions given in Example 6.7 are universal in the sense that every poset is isomorphic to a poset of each of the four types. Do you see why? If you get stuck answering this, we will revisit the question at the end of the chapter, and we will give you a hint.
An isomorphism from \(\bfP\) to \(\bfP\) is called an automorphism of \(\bfP\text{.}\) An isomorphism from \(\bfP\) to a subposet of \(\bfQ\) is called an embedding of \(\bfP\) in \(\bfQ\text{.}\) In most settings, we will not distinguish between isomorphic posets, and we will say that a poset \(\PXP\) is contained in \(\QYQ\) (also \(\bfQ\) contains \(\bfP\)) when there is an embedding of \(\bfP\) in \(\bfQ\text{.}\) Also, we will say that \(\bfP\) excludes \(\bfQ\) when no subposet of \(\bfP\) is isomorphic to \(\bfQ\text{,}\) and we will frequently say \(\bfP=\bfQ\) when \(\bfP\) and \(\bfQ\) are isomorphic.
With the notion of isomorphism, we are lead naturally to the notion of an “unlabeled” posets, and in Figure 6.13, we show a diagram for such a poset.
Figure 6.13. An Unlabeled Partially Ordered Set

Discussion 6.14.

How hard is it to tell whether two posets are isomorphic? Bob thinks it’s not too difficult. Bob says that if you give him a bijection between the ground sets, then he can quickly determine whether you have established that the two posets are isomorphic. Alice senses that Bob is confusing the issue of testing whether two posets are isomorphic with simply verifying that a particular bijection can be certified to be an isomorphism. The first problem seems much harder to her. Carlos says that he thinks it’s actually very hard and that in fact, no one knows whether there is a good algorithm.
Note that the poset shown in Figure 6.13 has the property that there is only one maximal point. Such a point is sometimes called a one, denoted not surprisingly as \(1\text{.}\) Also, there is only one minimal point, and it is called a zero, denoted \(0\text{.}\)
The dual of a partial order \(P\) on a set \(X\) is denoted by \(P^d\) and is defined by \(P^d=\{(y,x):(x,y)\in P\}\text{.}\) The dual of a poset \(\PXP\) is denoted by \(\bfP^d\) and is defined by \(\bfP^d=(X,P^d)\text{.}\) A poset \(\bfP\) is self-dual if \(\bfP=\bfP^d\text{.}\)
A poset \(\PXP\) is connected if its comparability graph is connected, i.e., for every \(x,y\in X\) with \(x\ne y\text{,}\) there is a finite sequence \(x=x_0,x_1,\dots,x_n=y\) of points from \(X\) so that \(x_i\) is comparable to \(x_{i+1}\) in \(P\) for \(i=0,1,2,\dots,n-1\text{.}\) A subposet \((Y,P(Y))\) of \((X,P)\) is called a component of \(\bfP\) if \((Y,P(Y))\) is connected and there is no subset \(Z\subseteq X\) containing \(Y\) as a proper subset for which \((Z,P(Z))\) is connected. A one-point component is trivial (also, a loose point or isolated point); components of two or more points are nontrivial. Note that a loose point is both a minimal element and a maximal element. Returning to the poset shown in Figure 6.5, we see that it has two components.
It is natural to say that a graph \(\bfG\) is a comparability graph when there is a poset \(\PXP\) whose comparability graph is isomorphic to \(\bfG\text{.}\) For example, we show in Figure 6.15 a graph on \(6\) vertices which is not a comparability graph. (We leave the task of establishing this claim as an exercise.)
Figure 6.15. A Graph Which is Not a Comparability Graph
Similarly, we say that a graph \(\bfG\) is a cover graph when there exists a poset \(\PXP\) whose cover graph is isomorphic to \(\bfG\text{.}\) Not every graph is a cover graph. In particular, any graph which contains a triangle is not a cover graph. In the exercises at the end of the chapter, you will be asked to construct triangle-free graphs which are not cover graphs—with some hints given as to how to proceed.

Discussion 6.16.

Bob is quite taken with graphs associated with posets. He makes the following claims.
  1. Only linear orders have paths as cover graphs.
  2. A poset and its dual have the same cover graph and the same comparability graph.
  3. Any two posets with the same cover graph have the same height and the same width.
  4. Any two posets with the same comparability graph have the same height and the same width.
Alice shrugs and says that Bob is right half the time. Which two assertions are correct?
Undeterred, Bob notes that the comparability graph shown in Figure 6.9 is also an incomparability graph (for another poset). He goes on to posit that this is always true, i.e., whenever \(\bfG\) is the comparability graph of a poset \(\bfP\text{,}\) there is another poset \(\bfQ\) for which \(\bfG\) is the incomparability graph of \(\bfQ\text{.}\) Alice says that Bob is right on the first count but she is not so sure about the second. Dave mumbles that they should take a look at the comparability graph of the third poset in Figure 6.8. This graph is not an incomparability graph. But in his typical befuddled manner, Dave doesn’t offer any justification for this statement. Can you help Alice and Bob to see why Dave is correct?
Bob is on a roll and he goes on to suggest that it is relatively easy to determine whether a graph is a comparability graph (he read it on the web), but he has a sense that determining whether a graph is a cover graph might be difficult. Do you think he is right—on either count?