Assume $m$ and $n$ are to natural numbers. Prove that in a sequence of $mn+1$ numbers, there is an ascending sequence with length of $n+1$ or a descending sequence with length of $m+1$

How can i prove this statement?

  • 3
    $\begingroup$ See this page. It doesn't give a proof but should help. $\endgroup$ – Carl Schildkraut May 16 '17 at 21:54

Let $\{a_i\}$ be a sequence of $mn+1$ terms.

If there is an increasing sequence of length $n+1$, then the conclusion holds. Therefore, lets assume there is not an increasing sequence of length $n+1$.

Let $l(i)$ denote the length of the longest increasing subsequence ending at $a_i$. Since there is no increasing sequence of length $n+1$, we see that for each term index $i$, $l(i)$ is an integer such that $1 \leq l(i) \leq n$.

Since there are $mn+1$ terms in the sequence, there are $mn+1$ values $l(i)$ to consider. Each $l(i)$ can be one of $n$ values. By the Pigeonhole Principle, there are $m+1$ indices that have the same value for $l(i)$.

We order the indices as follows: $$ i_1 < i_2 <i_3 < \cdots < i_m < i_{m+1} $$ and we have that $$ l(i_1)= l(i_2)=l(i_3)= \cdots=l(i_m) =l(i_{m+1}) = L$$ The claim is that the terms selected by these indices form a decreasing sequence, that is: $$ a_{i_1} > a_{i_2} > a_{i_3} > \cdots > a_{i_m} > a_{i_{m+1}} $$ We show this by contradiction. Assume there are two indices $i_{k_1}$ and $i_{k_2}$ such that: $$ i_{k_1} < i_{k_2} \quad \wedge \quad a_{i_{k_1}} \leq a_{i_{k_2}}$$ Then we see that, since $l(i_{k_1})=L$, we could take the term $a_{i_{k_2}}$ and create an increasing subsequence of length $L+1$ ending at this term, meaning $l(i_{k_2}) \geq L+1$. This contradicts that it must equal $L$. Therefore, the terms form a decreasing sequence: $$ a_{i_1} > a_{i_2} > a_{i_3} > \cdots > a_{i_m} > a_{i_{m+1}} $$

  • 1
    $\begingroup$ You should point to a reference of this prove among many proves of Erdős–Szekeres theorem $\endgroup$ – JJR May 16 '17 at 22:54

That is usually mentioned as the Erdos-Szekeres', or Dilworth's, theorem. Let us assume that $h_1,\ldots,h_{mn+1}$ is our sequence, with $h_a$ representing the height of the $a$-th person. Let us assume that these people have to go to a post office with $m$ queues. The first person arrives and takes place in the first empty queue. The second person arrives and if $h_2>h_1$ he/she takes place behind the first person, otherwise takes place in the first free queue. The process continues till placing $h_{mn}$. When $h_{mn+1}$ arrives, only two mutually exclusive things might happen:

  1. $h_{mn+1}$ is able to take place in some queue. In such a case there are $mn+1$ people in $m$ queues, hence some queue is made by at least $n+1$ people, and it gives an increasing subsequence;
  2. $h_{mn+1}$ is not able to take place in any queue. Then the last person in every queue and $h_{mn+1}$ form a decreasing subsequence of $m+1$ terms.

This theorem can be used to give an unconventional proof of the Bolzano-Weierstrass theorem, for instance. Historically, it gave a fundamental Lemma for tackling the happy ending problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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