Problem: Prove the following: a sequence of $rs + 1$ real numbers has an increasing subsequence of length $r + 1$ or a decreasing subsequence of length $s + 1$.
Solution: Define a partial ordering on the sequence $a _ { 1 } , \ldots , a _ { r s + 1 }$ by $a _ { i } \preceq a _ { j }$ iff, $a _ { i } \leq a _ { j }$ and $i \leq j$ A chain is an increasing subsequence, an antichain is a decreasing subsequence. Now I would like to apply Dilworth theorem. Suppose that the maximum size of a chain is $r+1$, the poset can be partitioned into $r+1$ antichain. However from there I don't now how to continue, what would be size of those antichains?
Best Answer
Assume that the maximum size of an antichain is $\le s$. Then the poset can be partitioned into at most $s$ chains. By pigeonhole principle, there is at least one chain of size $\ge \lceil \frac{rs+1}{s}\rceil= r+1. $ Thus either there is a chain of size $\ge r+1$ or an antichain of size $\ge s+1$.