Dilworth's theorem application

Question

I need to prove the following:

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

I understand the statement of Dilworth's theorem, but don't really know how to apply it to this problem. I would really appreciate a hint to could lead me to start setting up the problem.

Answer 1

HINT: Let $P=\{\langle k,a_k\rangle:k=1,\ldots,n^2+1\}$. For $\langle k,a_k\rangle,\langle\ell,a_\ell\rangle\in P$ write $\langle k,a_k\rangle\preceq\langle\ell,a_\ell\rangle$ if and only if $k\le\ell$ and $a_k\le a_\ell$. $\langle P,\preceq\rangle$ is a partial order.

• A chain in $P$ corresponds to what kind of subsequence of the permutation?
• What about an antichain in $P$?
• If each chain in $P$ has length at most $n$, then ... ?