6.10: Exercises
- Page ID
- 97896
1. We say that a relation \(R\) on a set \(X\) is symmetric if \((x,y) \in R\) implies \((y,x) \in R\) for all \(x,y \in X\). If \(X=\{a,b,c,d,e,f\}\), how many symmetric relations are there on \(X\)? How many of these are reflexive?
2. A relation \(R\) on a set \(X\) is an equivalence relation if \(R\) is reflexive, symmetric, and transitive. Fix an integer \(m \geq 2\). Show that the relation defined on the set \(\mathbb{Z}\) of integers by \(aRb (a,b \in \mathbb{Z})\) if and only if \(a≡b(mod m)\) is an equivalence relation. (Recall that \(a≡b(mod m\)) means that when dividing \(a\) by \(m\) and \(b\) by \(m\) you get the same remainder.)
\(P=\{(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(2,5),(4,5),(3,5),(1,5)\}\)
a partial order on the set \(X=\{1,2,3,4,5\}\)? If so, discuss what properties you verified and how. If not, list the ordered pairs that must be added to \(P\) to make it a partial order or say why it cannot be made a partial order by adding ordered pairs.
4. Draw the diagram of the poset \(\textbf{P}=(X,P)\) where \(X=\{1,2,3,5,6,10,15,30\}\) and \(x \leq y\) in \(P\) if and only if \(x|y\). (Recall that \(x|y\) means that \(x\) evenly divides \(y\) without remainder. Equivalently \(x|y\), if and only if \(y≡0\) (mod \(x\)).)
5. Draw the diagram of the poset \(\textbf{P}=(X,P)\) where
\(X=\{\{1,3,4,5,6\},\{1,2,4,5,6\},\{1,2,3,6\},\{1,2,3\},\{1,5,6\},\{1,3,6\},\{1,2\},\{1,6\},\{3,5\},\{1\},\{3\},\{4\}\}\)
and \(P\) is the partial order on \(X\) given by the “is a subset of” relationship.
6. A linear extension of a poset \(\textbf{P}=(X,P)\) is a total order \(L\) on \(X\) such that if \(x \leq y\) in \(P\), then \(x \leq y\) in \(L\). Give linear extension of the three posets shown in Figure 6.8. If you feel very ambitious, try to count the number of linear extensions of the poset on the left side of the figure. Don't list them. Just provide an integer as your answer.
7. Alice and Bob are considering posets \(\textbf{P}\) and \(\textbf{Q}\). They soon realize that \(\textbf{Q}\) is isomorphic to \(\textbf{P}^d\). After 10 minutes of work, they figure out that \(\textbf{P}\) has height 5 and width 3. Bob doesn't want do find the height and width of \(\textbf{Q}\), since he figures it will take (at least) another 10 minutes to answer these questions for \(\textbf{Q}\). Alice says Bob is crazy and that she already knows the height and width of \(\textbf{Q}\). Who's right and why?
8. For this exercise, consider the poset \(\textbf{P}\) in Figure 6.5.
a. List the maximal elements of \(\textbf{P}\).
b. List the minimal elements of \(\textbf{P}\).
c. Find a maximal chain with two points in \(\textbf{P}\).
d. Find a chain in \(\textbf{P}\) with three points that is not maximal. Say why your chain is not maximal.
e. Find a maximal antichain with four points in \(\textbf{P}\).
9. Find the height \(h\) of the poset \(\textbf{P}=(X,P)\) shown below as well as a maximum chain and a partition of \(X\) into \(h\) antichains using the algorithm from this chapter.
11. A restaurant chef has designed a new set of dishes for his menu. His set of dishes contains 10 main courses, and he will select a subset of them to place on the menu each night. To ensure variety of main courses for his patrons, he wants to guarantee that a night's menu is neither completely contained in nor completely contains another night's menu. What is the largest number of menus he can plan using his 10 main courses subject to this requirement?
12. Draw the diagram of the interval order represented in Figure 6.34.
13. Draw the diagram of the interval order represented in Figure 6.35.
14. Find an interval representation for the poset in Figure 6.36 or give a reason why one does not exist.
15. Find an interval representation for the poset in Figure 6.37 or give a reason why one does not exist.
16. Find an interval representation for the poset in Figure 6.38 or give a reason why one does not exist.
17. Find an interval representation for the poset in Figure 6.39 or give a reason why one does not exist.
18. Use the First Fit algorithm (ordering by left endpoints) to find the width \(w\) of the interval order shown in Figure 6.40 and a partition into \(w\) chains. Also give an antichain with \(w\) points.
19. Complete the proof of Theorem 6.30.
- Hint
-
The key idea is to show that if \(d\) is the least positive integer for which an interval order \(\textbf{P}\) has a representation using end points from \(\{1,2,…,n\}\), then every integer \(i\) from this set must be both a left end point and a right end point of an interval.
20. Show that every poset is isomorphic to a poset of each of the four types illustrated in Example 6.7.
- Hint
-
For each element \(x\), choose some unique identifying key which is an element/prime/coordinate/observer. Then associate with \(x\) a structure that identifies the keys of elements from \(D[x]\).
21. The dimension of a poset \(\textbf{P}=(X,P)\), denoted dim(\(\textbf{P}\)), is the least \(t\) for which \(P\) is the intersection of \(t\) linear orders on \(X\).
a. Show that the dimension of a poset \(\textbf{P}\) is the same as the dimension of its dual.
b. Show that \(\textbf{P}\) is a subposet of \(\textbf{Q}\), then dim(\(\textbf{P}\))≤dim(\(\textbf{Q}\)).
c. Show that the removal of a point can reduce the dimension by at most 1.
d. Find the dimension of the posets in Figure 6.8.
e. Use Dilworth's theorem to show that the dimension of a poset is at most its width.
f. Use the example on the left side of Figure 6.33 to show that for every \(n \geq 2\), there exists a poset \(\textbf{P}_n\) on \(2n\) points having width and dimension equal to \(n\).