Let S be a sequence of n different numbers. A subsequence of S is a sequence that can be obtained by deleting elements of S. For example, if S is 6,4,7,9,1,2,5, 3,8), then 6, 4, 7) and (7,2,5, 3) are both sub- sequences of S. An increasing subsequence of S is a subsequence of whose successive elements get larger. For example, (1, 2, 3, 8) is an increasing subsequence of S. Decreasing subse- quences are defined similarly; (6,4,1) is a decreasing subsequence of S. And let A be the set of numbers in S. (So A is (1,9) for the example above.) There are two straightforward linear orders for A. The first is numerical order where A is ordered by the < relation. The second is to order the elements by which comes first in S; call this order 6 Let < be the product relation of the linear orders So < is a partial order on A.
(a) List all the maximum-length increasing subsequences of S, and all the maximum- length decreasing subsequences.
(b) Draw a diagram of the partial order on A. What are the maximal and minimal elements?
(c) Explain the connection between increasing and decreasing subsequences of S, and chains and anti-chains under <.
(d) Prove that every sequence of length n has an increasing subsequence of length greater than (n)^1/2 or a decreasing subsequence of length at least (n)^1/2.