1. ## Dilworth’s theorem

Hi Guys I really in trouble with a problem about dilwor theorem

The problem states:

Let $a_1 , a_2 , . . . , a_{
n^2 +1}$
be a permutation of the integers
$1, 2, . . . , n^2 + 1$. Show that Dilworth’s theorem implies that the
sequence has a subsequence of length $n + 1$ that is monotone.

Thanks a lot to all of you

All the best

joksy

2. Originally Posted by joksy
Hi Guys I really in trouble with a problem about dilwor theorem

The problem states:

Let $a_1 , a_2 , . . . , a_{
n^2 +1}$
be a permutation of the integers
$1, 2, . . . , n^2 + 1$. Show that Dilworth’s theorem implies that the
sequence has a subsequence of length $n + 1$ that is monotone.

Thanks a lot to all of you

All the best

joksy
Hi joksy,

Here's a hint.

I think the trick is to define a partial order on ${1, 2, \dots , n^2+1}$ as follows:

Define $i \leq j$ if
$i \leq j \text{ and } a_i \leq a_j$ (in the usual ordering of the integers).

Think about what constitutes a chain and an antichain in this ordering (in relation to ascending or descending subsequences), then apply Dilworth's theorem, and I think you will get it.