# Reduction to Dilworth's Lemma

I am working on a hw exercise and would like to check if I understand it fully. I don't trust myself.

Problem: Let $n^2 + 1$ points be given in $\mathbb{R}^2$. Prove that there is a sequence of $n + 1$ points $(x_1, y_1), \ldots, (x_{n+1}, y_{n+1})$ for which $x_1 \leq x_2 \leq \cdots \leq x_{n+1}$ and $y_1 \geq y_2 \geq \cdots \geq y_{n+1}$ or a sequence of $n + 1$ points for which $x_1 \leq x_2 \leq \cdots \leq x_{n+1}$ and $y_1 \leq y_2 \leq \cdots \leq y_{n+1}$.

Proof: Define a partial ordering $\preceq$ over $\mathbb{R^2}$ by $(x_1, y_1) \preceq (x_2, y_2) \implies x_1 < x_2$ or $x_1 = x_2 \text{ and } y_1 \leq y_2$. Apply Dilworths Lemma, which says that given a poset of size $k \geq rs + 1$ there will be a chain of length $s + 1$ or anti-chain of length $r + 1$. Let $s = r = n$ and we have $n^2 + 1$ elements required along with the existence of a chain or anti-chain of length $n + 1$.

Am I missing any steps?

-

## 1 Answer

Your $\preceq$ is simply the lexicographic order on $\mathbb{R}^2$, so it’s a linear order, and therefore every antichain has cardinality $1$. In particular, if $x_1\le\dots\le x_{n+1}$ and $y_1\ge\dots\ge y_{n+1}$, the points $(x_1,y_1),\dots,(x_{n+1},y_{n+1})$ aren’t an antichain in your $\langle\mathbb{R}^2,\preceq\rangle$. Can you think of another partial order on $\mathbb{R}^2$, also easily defined in terms of the ordering of the individual coordinates, that would make $\{(x_1,y_1),\dots,(x_{n+1},y_{n+1})\}$

$$\begin{cases} \text{a chain},&\text{ if }x_1\le\dots\le x_{n+1}\text{ and }y_1\le\dots\le y_{n+1}\\ \text{an antichain},&\text{ if }x_1\le\dots\le x_{n+1}\text{ and }y_1\ge\dots\ge y_{n+1}\;? \end{cases}$$

If you’re still stuck after thinking about it for a while, feel free to ask for more details.

-
If we let $\preceq$ be$(x_1, y_1) \preceq (x_2, y_2) \implies x_1 \leq x_2 \text{ and } y_1 \leq y_2$. But couldn't an anti-chain then be a sequence of increasing x values? Additionally, what would the case be for non-decreasing x values, and all equivalent y values? that falls into both chain and anti-chain? – Nicholas Mancuso Feb 9 '12 at 5:09
@Nicholas: Only if the $y$ values are strictly decreasing. (And yes, that’s the order that I had in mind.) – Brian M. Scott Feb 9 '12 at 5:14