I need an explanation of this proof of Erdos-Szekeres theorem given here.
The proof says-
Place an element of the sequence in a box labelled $r$ if the longest increasing subsequence beginning with that element has $r$ terms. If there is no subsequence with $m$ terms, we need only $m − 1$ boxes. By the pigeonhole principle, the placement of $(m − 1)(n − 1) + 1$ elements in these boxes yield a box with at least $n$ elements. These $n$ terms form a decreasing subsequence since any two terms forming an increasing subsequence belong to different boxes.
Now I cant understand this line-"These $n$ terms form a decreasing subsequence since any two terms forming an increasing subsequence belong to different boxes."
Also, I cannot understand this addendum-"To see that this result is best possible, consider the sequence of intervals $(I_1, . . . I_{n−1})$ where $I_k :=[(n − 1 − k)(m − 1) + 1,(n − k)(m − 1)].$ This sequence consists of $(m − 1)(n − 1)$ distinct integers and has neither an increasing subsequence with $m$ terms nor a decreasing subsequence with $n$ terms."
Is it necessary to include this addendum in a general proof of Erdos-Szekeres Theorem?
The last addendum is not necessary for a proof, just for motivation, and to show we have a "best possible" result. Normally I'd expect it before the proof, in a separate discussion.
The first remark is quite easy if you think about it: if $x_i < x_j$ (for some $i<j$) then if $x_j$ had an increasing subsequence starting from it of length $k$ and no longer one, then $x_i$ has at least an increasing sequence starting from it of length $k+1$ (start with $x_i, x_j$ and continue with the previous one from $x_j$), so $x_j$ will be in box $k$, and $x_i$ will be in box $k+1$ (or higher).
So all sequence pairs from one box cannot form an increasing pair, so they all are decreasing pairs, and the box (when viewed as a subsequence) is decreasing.