Let's review a few definitions:
Dilwoths's theorem: Suppose that the length of the longest antichain in the poset $P$ is $r$, then $P$ can be partitioned into $r$ chains.
Dilworth's dual theorem: Suppose that the length of the longest chain in the poset $P$ is $r$, then $P$ can be partitioned into $r$ antichains.
Erdős-Szekeres theorem: Given $n \geq rs+1$, any sequence of $n$ elements has either an increasing subsequence of length $r+1$ or a decreasing subsequence of lengthe $s+1$.
Now here's the proof:
Define a partial ordering on the members of the sequence, in which $x$ is less than or equal to $y$ in the partial order if $x ≤ y$ as numbers and $x $ is not later than $y$ in the sequence. A chain in this partial order is a monotonically increasing subsequence, and an antichain is a monotonically decreasing subsequence. By Dilworth's dual theorem, either there is a chain of length $r$, or the sequence can be partitioned into at most $r − 1$ antichains; but in that case the largest of the antichains must form a decreasing subsequence with length at least
$$\lceil\frac{rs-r-s+2}{r-1} \rceil =s.$$
Alternatively, by Dilworth's theorem itself, either there is an antichain of length $s$, or the sequence can be partitioned into at most $s − 1$ chains, the longest of which must have length at least $r$.
What I really don't comprehend about this proof, is the relation between the definitions and the bolded part, which is supposedly deduced from the definitons.
Any help would be appreciated.
Best Answer
The proof actually starts with a sequence of length $n\ge(r-1)(s-1)+1$ and shows that it has either an increasing subsequence of length $r$ or a decreasing subsequence of length $s$. (In other words, it shifts the $r$ and $s$ of the usual statement of the theorem by $1$.)
Suppose that there is no chain of length $r$ in the given partial order. Then the maximal length of any chain is at most $r-1$, and by the dual Dilworth theorem the partial order can be partitioned into at most $r-1$ antichains. The partial order has at least
$$(r-1)(s-1)+1=rs-r-s+2$$
elements; if you divide these into $r-1$ or fewer parts, the mean part size is at least
$$\frac{rs-r-s+2}{r-1}=\frac{(r-1)(s-1)+1}{r-1}=s-1+\frac1{r-1}\;,$$
so the largest part must be at least
$$\left\lceil\frac{rs-r-s+2}{r-1}\right\rceil=\left\lceil s-1+\frac1{r-1}\right\rceil=s-1+\left\lceil\frac1{r-1}\right\rceil=s-1+1=s\;.$$
The second part of the argument is virtually identical, with the rôles of $r$ and $s$ interchanged and using Dilworth’s theorem rather than its dual.