0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.