# Thread: Dilworth’s theorem

1. ## Dilworth’s theorem

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

The problem states:

Let $\displaystyle a_1 , a_2 , . . . , a_{ n^2 +1}$ be a permutation of the integers
$\displaystyle 1, 2, . . . , n^2 + 1$. Show that Dilworth’s theorem implies that the
sequence has a subsequence of length $\displaystyle 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 $\displaystyle a_1 , a_2 , . . . , a_{ n^2 +1}$ be a permutation of the integers
$\displaystyle 1, 2, . . . , n^2 + 1$. Show that Dilworth’s theorem implies that the
sequence has a subsequence of length $\displaystyle 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 $\displaystyle {1, 2, \dots , n^2+1}$ as follows:

Define $\displaystyle i \leq j$ if
$\displaystyle 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.