1 Posets: 10 points

We learned in lecture that a poset can be thought of as a digraph where every vertex corresponds to an element in the poset, and every edge (a, b) corresponds to the the precedence constraint a ⪯ b. Since the precedence relation is transitive, we leave out the edges which can be inferred by transitivity and reflexivity. This digraph is called the Haase diagram for the poset.

Let A, B be posets with associated ordering operation ⪯. Define A ⊕ B to be the poset consisting of all the elements of A and B, all the precedence constraints of A and B, as well as all the additional precedence constraints necessary to insure that ∀a ∈ A, b ∈ B, a ⪯ b, without changing the precedence constraints within A or B.

Recall that a minimal element of X is an element x_{1} ∈ X such that ∀x_{2} ∈ X, x_{1} ≠ x_{2}, x_{1} ⪯ x_{2}, or x_{1} and x_{2} are incomparable. A maximal element of X is an element x_{1} ∈ X such that ∀x_{2} ∈ X, x_{1} ≠ x_{2}, x_{2} ⪯ x_{1}, or x_{1} and x_{2} are incomparable.

Figure 1: A = {a,b,c}, {(a,c),(b,c)} B = {1,2,3,4}, {(1,3),(2,3),(1,4)}

Figure 1:

Figure 2: A = {a,b,c,d}, {(a,b),(a,c),(c,d)} B = {1,2,3,4}, {(1,4),(2,4),(3,4)}

Figure 2:

a. (1 point) Given the posets A, B in figure 1, how many edges must be added to form A ⊕ B?

Soln. We must add (c, 1), (c, 2) for a total of 2 edges.

b. (1 point) Given the posets A, B in figure 2, how many edges must be added to form A ⊕ B?

Soln. We must add (b, 1), (b, 2), (b, 3), (d, 1), (d, 2), (d, 3) for a total of 6 edges.

c. (3 points) If x = |{a : a is a minimal element of A}| and y = |{b : b is a maximal element of B}|, how many edges must be added to form A ⊕ B in terms of |A|, |B|, x, and y?

Soln. xy

d. (5 points) Prove your answer from part (c).

Soln. Let E = {(a, b) : a is a minimal element of A and b is a maximal element of B}. Clearly |E| = xy. First note that E satisifies the necessary constraints (i.e., it’s big enough). Now we prove that we need every single element of E.

Consider two elements c, d, where c is a minimal element of A, and d is a minimal element of B. Let e be the edge between them in E. Can we take away e? We could only if c ⪯ d was inferrable from other edges. (I.e., it was a transitive consequence of other precedence constraints.) If we can infer this from some other set of edges, that means we can find precedence constraints (c, e) and (e, d). Since c is a minimal element of A, e must be in B. However, since d is a maximal element of B, e must be in A. Thus no such e exists, and thus we need every edge in E.

Thus exactly xy additional edges are needed to form A ⊕ B.