Partially Ordered Sets

Linear extensions and dual orders, maximal and minimal elements, long chains, and finding the width of a poset with a matching antichain and chain partition.

Applied Combinatorics, Partially Ordered Sets

Status

FlagsLoading your progress…

5 exercises

Exercise 6

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 this figure. 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.

2.5

Exercise 7

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 a…

2.5

Exercise 8

For this exercise, consider the poset $\bfP$ in this figure.

List the maximal elements of $\bfP$ .
List the minimal elements of $\bfP$ .
Find a maximal chain with two points in $\bfP$ .
Find a chain in $\bfP$ with three points that is not maximal. Say why your chain is not maximal.
Find a maximal antichain with four points in $\bfP$ .

2.5

Exercise 10

For each of the two distinct (up to isomorphism) posets in this figure, find the width $w$ , an antichain of size $w$ , and a partition of the ground set into $w$ chains.

2.5

Exercise 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 u…

2.5