maths.free › Combinatorics & Graph Theory › 6. Partially Ordered Sets › Partially Ordered Sets: exercises

Partially Ordered Sets: exercises

Partially Ordered Sets: exercises — from Keller & Trotter, Applied Combinatorics.

Practice (39)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

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?
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 \(\ints\) of integers by \(aRb\) (\(a,b\in\ints\)) if and only if \(a\equiv b\pmod{m}\) is an equivalence relation. (Recall that \(a\equiv b\pmod{m}\) means that when dividing \(a\) by \(m\) and \(b\) by \(m\) you get the same remainder.)
Is the binary relation \[\begin{aligned}\end{aligned}\] 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.
Draw the diagram of the poset \(\bfP=(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\equiv 0\pmod{x}\).)
Draw the diagram of the poset \(\PXP\) where \[\begin{aligned}\end{aligned}\] and \(P\) is the partial order on \(X\) given by the is a subset of relationship.
A linear extension of a poset \(\bfP=(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 . 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.

Zbulo përgjigjen

There are many linear extensions for each of these posets, so we just give one for each of these posets. For ease of formatting, they are written horizontally with the smallest element at the left: \[\begin{aligned}\end{aligned}\] \[\begin{aligned}\end{aligned}\] \[\begin{aligned}\end{aligned}\]
The count for the rightmost poset is reasonable to do. There's a unique chain of 4 points that has to be in that order and the three points not in that chain form an antichain. (I'm going to omit parentheses and commas when writing the elements here.) If we have both 573 at the top of the linear extension and 415 at the bottom of the linear extension, then there are three spots for 254, so 3 linear extensions in this case. If 573 is at the top of the linear extension but 415 is not at the bottom, then there are two choices for where to put 415 and after doing that, there are 4 spots for where to put 254, which results in 8 linear extensions for this case. The case with 415 at the bottom and 573 not at the top is dual, so 8 more. If we have 767 at the top and 121 at the bottom (the only remaining scenario), then there are 5 ways to place 573 and 415 into the 4-point chain (listing them out is the quickest way to see this, I think). Once that is done, there are 5 spots for 254 to go, so 25 linear extensions in this case. Thus, there are 44 in total.
The count for the left-hand poset, which is isomorphic to the middle poset, is harder. Using software, there are 73 linear extensions. A reasonable attempt probably splits things up into some cases based on what happens with the minimal elements. To work a bit crudely on a lower bound, you could note that the order diagram is drawn with three "layers" of antichains, so there must be at least \(2!3!2! = 24\) linear extensions if we just focus on keeping the layers together. But then notice that \(\{2,3,11\}\) is also maximal, so we could have drawn it in the top layer. If we want to ensure we don't count anything we've already counted, we need to think of putting \(\{2,3,11\}\) above at least one of \(\{2,3,5,7\}\) and \(\{2,5,25\}\). So then there's \(2!2!\cdot 2\cdot 2! = 16\) more linear extensions here (order the minimal elements, order the two remaining middle layer elements, pick which of \(\{2,3,5,7\}\) and \(\{2,5,25\}\) comes next, order the other one of those with \(\{2,3,11\}\)). One could continue working at this by recognizing that the two minimal elements of the poset not need be the lowest two elements in a linear extension, and so on.
Alice and Bob are considering posets \(\bfP\) and \(\bfQ\). They soon realize that \(\bfQ\) is isomorphic to \(\bfP^d\). After \(10\) minutes of work, they figure out that \(\bfP\) has height \(5\) and width \(3\). Bob doesn't want do find the height and width of \(\bfQ\), since he figures it will take (at least) another \(10\) minutes to answer these questions for \(\bfQ\). Alice says Bob is crazy and that she already knows the height and width of \(\bfQ\). Who's right and why?

Zbulo përgjigjen

Alice is correct. Recall that \(\mathbf{P}\) and \(\mathbf{P}^{d}\) have the same comparability graph and the same incomparability graph. Recall also that the width of a poset is the clique number of its incomparability graph while the height of a poset is the clique number of its comparability graph. Thus, the width of \(\mathbf{P}^{d}\) is the same as the width of \(\mathbf{P}\) and the heights are also equal. (One could also explain this by noting that the order diagram of \(\mathbf{P}^{d}\) is obtained from the order diagram of \(\mathbf{P}\) by rotating it \(180^{\circ}\) and that this transformation preserves chains and antichains, so the height and width are unchanged.)
For this exercise, consider the poset \(\bfP\) in .
1. List the maximal elements of \(\bfP\).
2. List the minimal elements of \(\bfP\).
3. Find a maximal chain with two points in \(\bfP\).
4. Find a chain in \(\bfP\) with three points that is not maximal. Say why your chain is not maximal.
5. Find a maximal antichain with four points in \(\bfP\).
Zbulo përgjigjen
1. The maximal elements are those that are not less than any other element: 15,8,11,2,17,3.
2. The minimal elements are those that are not greater than any other element: 16,1,5,14.
3. Since \(\{16,8\}\) consists of a minimal element and a maximal element and 8 covers 16, this is a maximal chain with two points.
4. The chain \(\{5,10,2\}\) contains three points but is not maximal because \(5\leq 4\leq 10\), so we could add 4 to this set and still have a chain.
5. The antichain \(\{16,1,5,14\}\) is maximal because it contains all the minimal elements and thus no other points can be added.
Find the height \(h\) of the poset \(\PXP\) shown below as well as a maximum chain and a partition of \(X\) into \(h\) antichains using the algorithm from this chapter.

Zbulo përgjigjen

Applying the algorithm where we label the minimal elements, remove those points, label the minimal elements of what's left, remove those points, etc., we get the following partition into antichains: \[\begin{aligned}A_1 \amp = \{22,18,23,12,16\} \\ A_2 \amp = \{2,3,13,17,11,21\} \\ A_3 \amp = \{4,25,10\} \\ A_4 \amp = \{5,24,8\} \\ A_5 \amp = \{20\} \\ A_6 \amp = \{19,9\} \\ A_7 \amp = \{6,7\} \\ A_8 \amp = \{1,26\} \\ A_9 \amp = \{14,15\}\end{aligned}\] Thus, the height is 9 which is witnessed by the 9-element chain \(\{15,26,7,9,20,5,4,3,22\}\).
For each of the two distinct (up to isomorphism) posets in , find the width \(w\), an antichain of size \(w\), and a partition of the ground set into \(w\) chains.

Zbulo përgjigjen

For the two isomorphic posets on the left, let's use the middle one. One three-element antichain is \(\{10,66,21\}\), but there are others. A possible partition into 3 chains is \(C_{1} = \{2,10,50\}\), \(C_{2} = \{66\}\), and \(C_{3} = \{3,21,210\}\). Thus, the width is 3.
For the right-hand poset, one three-element antichain is \(\{(2,5,4),(5,7,3),(4,1,5)\}\). A possible partition into 3 chains is \(C_{1} = \{(2,5,4)\}\), \(C_{2} = \{(1,2,1),(3,3,2),(5,7,3)\}\), and \(C_{3} = \{(4,1,5),(6,4,5),(7,6,7)\}\). Thus, the width is 3.
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?

Zbulo përgjigjen

We can view a menu as a subset of the list of 10 possible main courses. To avoid a menu that is contained in or contains another night's menu, we need to find a collection of subsets (menus) so that no subset is a subset of any other. That means we need an antichain in \(\mathbf{2}^{10}\). By Sperner's Theorem, we know that the width of \(\mathbf{2}^{10}\), which is the number of points in a maximum antichain, is \(C(10,5) = 252\). Thus, the largest number of menus he can plan subject to this requirement is 252.
Draw the diagram of the interval order represented in .
Draw the diagram of the interval order represented in .
Find an interval representation for the poset in or give a reason why one does not exist.
Find an interval representation for the poset in or give a reason why one does not exist.

Zbulo përgjigjen

This poset is not an interval order. There are many occurrences of \(\mathbf{2}+\mathbf{2}\). One example would be \(\set{1,3,8,4}\).
Find an interval representation for the poset in or give a reason why one does not exist.

Zbulo përgjigjen

We write out the down-sets and up-sets: \[\begin{aligned}D(1)\amp = \{2,7\}\amp U(1)\amp = \{6,8,9,11\} \\ D(2)\amp = \{7\}\amp U(2)\amp = \{1,3,5,6,8,9,10,11,12\} \\ D(3)\amp = \{2,4,7,10\}\amp U(3)\amp = \{\} \\ D(4)\amp = \{\}\amp U(4)\amp = \{3,6,8,9,10,11\} \\ D(5)\amp = \{2,7\}\amp U(5)\amp = \{8,9,11\} \\ D(6)\amp = \{1,2,4,7,10\}\amp U(6)\amp = \{9,11\} \\ D(7)\amp = \{\}\amp U(7)\amp = \{1,2,3,5,6,8,9,10,11,12\} \\ D(8)\amp = \{1,2,4,5,7,10,12\}\amp U(8)\amp = \{9,11\} \\ D(9)\amp = \{1,2,4,5,6,7,8,10,12\}\amp U(9)\amp = \{\} \\ D(10)\amp = \{2,4,7\}\amp U(10)\amp = \{3,6,8,9,11\} \\ D(11)\amp = \{1,2,4,5,6,7,8,10,12\}\amp U(11)\amp = \{\} \\ D(12)\amp = \{2,7\}\amp U(12)\amp = \{8,9,11\}\end{aligned}\] Putting the down-sets in ascending order and the up-sets in ascending order, we have \[\begin{aligned}\end{aligned}\] \[\begin{aligned}\end{aligned}\] Therefore, the the poset is an interval order and an interval representation is \[\begin{aligned}I(1)\amp = [3,5]\amp I(7)\amp = [1,1] \\ I(2)\amp = [2,2]\amp I(8)\amp = [7,7] \\ I(3)\amp = [5,8]\amp I(9)\amp = [8,8] \\ I(4)\amp = [1,3]\amp I(10)\amp = [4,4] \\ I(5)\amp = [3,6]\amp I(11)\amp = [8,8] \\ I(6)\amp = [6,7]\amp I(12)\amp = [3,6]\end{aligned}\]
Find an interval representation for the poset in or give a reason why one does not exist.
Use the First Fit algorithm (ordering by left endpoints) to find the width \(w\) of the interval order shown in and a partition into \(w\) chains. Also give an antichain with \(w\) points.

Zbulo përgjigjen

First Fit produces the chain partition below: \[\begin{aligned}C_{1}\amp = \{f,d,j,k,\} \\ C_{2}\amp = \{b,h,c,l,e,m,o\} \\ C_{3}\amp = \{g,n,a,i\}\end{aligned}\] The set \(\{n,l,j\}\) is one of many 3-element antichains, so because we have both the chain partition and the antichain of size 3, the width of this interval order is 3.
Complete the proof of .

Zbulo përgjigjen

Hint:
The key idea is to show that if \(d\) is the least positive integer for which an interval order \(\bfP\) has a representation using end points from \(\{1,2,\dots,n\}\), then every integer \(i\) from this set must be both a left end point and a right end point of an interval.
Show that every poset is isomorphic to a poset of each of the four types illustrated in .

Zbulo përgjigjen

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]\).
The dimension of a poset \(\PXP\), denoted \(\dim(\bfP)\), is the least \(t\) for which \(P\) is the intersection of \(t\) linear orders on \(X\).
1. Show that the dimension of a poset \(\bfP\) is the same as the dimension of its dual.
2. Show that \(\bfP\) is a subposet of \(\bfQ\), then \(\dim(\bfP)\le \dim(\bfQ)\).
3. Show that the removal of a point can reduce the dimension by at most\(1\).
4. Find the dimension of the posets in .
5. Use Dilworth's theorem to show that the dimension of a poset is at most its width.
6. Use the example on the left side of to show that for every \(n\ge2\), there exists a poset \(\bfP_n\) on \(2n\) points having width and dimension equal to \(n\).
I understood how Bob constructed his picture in the class preparation assignment.
Which of the following sets are antichains?
Which of the following sets are chains?
The set \(\{12,13,30,16\}\) is
The set \(\{3,25,10\}\) is
The set \(\{8,7,13,4,31,6,35\}\) is
If we find a chain \(C\) with 17 points in a poset \(\bfP\), then we know
How many points are there in \(\mathbf{2}^n\)?
How many minimal elements does \(\mathbf{2}^n\) have?
What is the height of \(\mathbf{2}^n\)?
Consider the intervals below as an interval order. Which intervals are less than \(k\) in the interal order?
Consider the intervals below as an interval order. Which intervals are incomparable to \(d\) in the interal order?
Which set forms a \(\mathbf{2}+\mathbf{2}\) in the poset below?
You've run the first four steps of the algorithm for an interval representation and have down-sets \[\begin{aligned}\end{aligned}\] and up-sets \[\begin{aligned}\end{aligned}\]. You know that \(D(f) = \{e\}\) and \(U(f) = \{d\}\). Then \(I(f)=\)
You're trying to find an interval representation for a poset and determine \(D(x)\not\subseteq D(z)\) and \(D(z)\not\subseteq D(x)\). You
Suppose that you're finding an interval representation for an interval order \(\mathbf{P}\) and determine that \(D(x) = D_1\), the smallest downset. Then you know
Consider the intervals in the order \(h,e,a,b,d,j,i,c,f,g\). How many chains does First Fit use?
You're chain partitioning this interval order using First Fit, ordering them by left endpoint with ties broken by smallest label. When you encounter \(h\), which points have you already assigned to chains?

Symbols used here

\int f(x)\,dx,\ \int_a^b

integral
Antiderivative (indefinite) or signed area from a to b (definite).

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\pm

plus or minus
Both signs at once: x = 3 ± 2 means 5 and 1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Provo timen.

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Më shumë në Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion–exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs