Mathematics for Computer Science

9.12. Summary of Relational Properties 275

Problem 9.31.
Letbe a partial order on a set,A, and let

AkWWDfajdepth.a/Dkg

wherek 2 N.

(a)Prove thatA 0 ;A 1 ;:::is a parallel schedule foraccording to Definition 9.10.5.

(b)Prove thatAkis an antichain.

Problem 9.32.
LetSbe a sequence ofndifferent numbers. AsubsequenceofSis a sequence that
can be obtained by deleting elements ofS.
For example, if
SD.6;4;7;9;1;2;5;3;8/

Then 647 and 7253 are both subsequences ofS(for readability, we have dropped
the parentheses and commas in sequences, so 647 abbreviates.6;4;7/, for exam-
ple).
Anincreasing subsequenceofSis a subsequence of whose successive elements
get larger. For example, 1238 is an increasing subsequence ofS. Decreasing sub-
sequences are defined similarly; 641 is a decreasing subsequence ofS.

(a)List all the maximum length increasing subsequences ofS, and all the maxi-
mum length decreasing subsequences.

Now letAbe thesetof numbers inS. (SoADf1;2;3;:::;9gfor the example
above.) There are two straightforward ways to path-total orderA. The first is to
order its elements numerically, that is, to orderAwith the<relation. The second
is to order the elements by which comes first inS; call this order<S. So for the
example above, we would have

6 <S4 <S7 <S9 <S1 <S2 <S5 <S3 <S 8

Next, define the partial orderonAdefined by the rule

aa^0 WWD a < a^0 anda <Sa^0 :

(It’s not hard to prove thatis strict partial order, but you may assume it.)

(b)Draw a diagram of the partial order,, onA. What are the maximal ele-
ments,... the minimal elements?