Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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