8
$\begingroup$

I have been studying Pigeonhole Principle and came across this theorem that is mentioned in the Discrete Mathematics book by Rosen. I understand the theorem and understand the example presented along with the same. But I am slightly confused by the what I understand to be the limitations in applicability of this theorem.

For example what about sequences that are not $n^2+1$ elements long, say sequences of length 11? While the theorem can be applied to sequences of length 10 by taking $n$ as 3 ($3^2+1=10$), I cannot find any $n$ such that $n^2+1=11$. Does that mean the theorem is not applicable in such cases? Does that mean there is no strictly increasing (or decreasing) subsequence of any particular length for any such sequences?

I read the theorem over and over again but it does seem like that the theorem is applicable to a very limited set of sequences i.e. sequences whose length can be written in form $n^2+1$. I was wondering if there was any possible relation between sequences of lengths that are not $n^2+1$ (say 7, 8, 9, 11 or 12) and the length of strictly increasing/decreasing sub-sequences that can be observed in such sequences.

$\endgroup$
2
  • $\begingroup$ E.g. any sequence Length $3^2+1=10$ must contain a strictly increasing or decreasing subsequence of length $3+1=4$ and similarly a sequence of length $4^2+1=17$ must have such a subsequence length $4+1=5$, all sequences with lengths >10 and <17 have a subsequence of at least length $3+1=4$ by the pigeonhole principle. This is what the theorem is saying, $\endgroup$
    – N. Shales
    Feb 18 '17 at 4:00
  • 1
    $\begingroup$ Erdos Szekeres Theorem $\endgroup$ Feb 18 '17 at 4:20
6
$\begingroup$

Take a sequence of length $11$ and remove one element of your choice. The theorem guarantees that the resulting sequence contains a sequence of $4$ either strictly increasing or strictly decreasing numbers. This subsequence is obviously present also in the original sequence of length $11$.

In general, find the largest $n$ such that $n^2+1$ is less than or equal to the length of your sequence. Then you can apply the pigeonholing theorem.

$\endgroup$
1
  • $\begingroup$ Ah. I should have thought about that. My bad. Thanks a ton. $\endgroup$ Feb 18 '17 at 4:07

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.