# proof for Erdős-Szekeres theorem using Dilworth's theorem

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.

## 2 Answers

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.

Erdős-Szekeres theorem: Given $$n≥rs+1$$, any sequence of $$n$$ elements has either an increasing subsequence of length $$r+1$$ or a decreasing subsequence of length $$s+1$$.

As mentioned by Brian M. Scott, the bold part in your proof is a proof for an equivalent formulation: given $$n \geq (r-1)(s-1)+1$$ for $$r,s \in \mathbb{Z}_{>0}$$, any sequence of $$n$$ distinct reals has either an increasing subsequence of length $$r$$ or a decreasing subsequence of length $$s$$.

To prove the original formulation ($$n \geq rs + 1$$): first define the same partially ordered set $$P$$ as you mentioned.

Case 1: there is a chain of length at least $$r+1$$ as desired.

Case 2: the longest chain has length $$\ell \leq r$$. By Dilworth's Dual Theorem (Mirsky's Theorem), we can partition $$P$$ into $$k$$ antichains, where $$k=\ell \leq r$$.

Suppose for contradiction that no antichain $$A_i$$ in the partition has length $$|A_i| \geq s+1$$. So $$|A_i| \leq s$$ for each $$A_i$$. So there can be at most $$rs$$ total elements in our antichain partition, since $$\sum_{i=1}^k|A_i|\leq\sum_{i=1}^ks=ks\leq rs$$. But our antichain partition must have $$|P| = n \geq rs+1$$ elements.

So some antichain in the partition has length at least $$s+1$$ as desired.