Exercise 18, § 5

(a) Let E be a finite ordered set with $p$ elements. If $m,n$ are two integers such that $mn < p$, show that E has either a totally ordered subset of $m$ elements or else a free subset (§ 1, Exercise 5) of $n$ elements (use § 4, Exercise 5).

(b) Let $h, k$ be two integers $\geqslant 1$ and let $r(h, k) = (h - 1)(k - 1) + 1$. Let I be a finite totally ordered set with at least $r(h,\ k)$ elements. Show that, for each finite sequence $(x_i)_{i \in I}$ of elements of a totally ordered set E, there exists either a subset H of $h$ elements of I such that the sequence $(x_i)_{i \in H}$ is increasing, or else a subset K of $k$ elements of I such that the sequence $(x_i)_{i \in K}$ is decreasing. (Use (a) applied to $I \times E$.)