Mathematics for Computer Science

9.11. Summary of Relational Properties 367

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 maximum-
length decreasing subsequences.

Now letAbe thesetof numbers inS. (SoAis the integersŒ1::9çfor the example
above.) There are two straightforward linear orders forA. The first is numerical
order whereAis ordered by 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
Letbe the product relation of the linear orders<sand<. That is,is defined
by the rule
aa^0 WWD a < a^0 AND a <Sa^0 :

Sois a partial order onA(Section 9.9).

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

(c)Explain the connection between increasing and decreasing subsequences ofS,
and chains and anti-chains under.

(d)Prove that every sequence,S, of lengthnhas an increasing subsequence of
length greater than

p

nor a decreasing subsequence of length at least

p

n.

(e)(Optional, tricky) Devise an efficient procedure for finding the longest in-
creasing and the longest decreasing subsequence in any given sequence of integers.
(There is a nice one.)

Problems for Section 9.10

Practice Problems

Problem 9.44.
For each of the following relations, decide whether it is reflexive, whether it is