I want to find an example of a sequence of n=rs distinct numbers where there is not an increasing sequence of length s or a decreasing sequence of length r, hence showing that the bound given by Erdős-Szekeres is the best possible.

However, having tried several options, I cannot come up with a single example. I thought of using r=1=s, but this gives a single element sequence which is both increasing and decreasing so does not work.

I am starting to think it cannot be possible. Is there such an example?

  • $\begingroup$ See here, here, or here for the case $r=s$; the idea is readily generalized. $\endgroup$ – Brian M. Scott Feb 11 '15 at 22:38
  • $\begingroup$ You are misstating the Erdős-Szekeres result. It says that, in a sequence of $rs+1$ distinct numbers, there is either a decreasing subsequence of length $r+1$ or an increasing subsequence of length $s+1$. This is best possible because you can construct a sequence of length $rs$ with no decreasing subsequence of length $r+1$ and no increasing subsequence of length $s+1$. $\endgroup$ – bof Feb 11 '15 at 22:48
  • $\begingroup$ I think there was a typo in the original result I was given. Makes sense I wasn't able to disprove it if what I was actually doing was within the bounds of the theorem! $\endgroup$ – AccioHogwarts Feb 24 '15 at 4:51

Take the sequence $\color{red}{r,r-1,r-2\dots 1},\color{blue}{2r,2r-1,2r-2\dots r+1} \dots \color{green}{rs,rs-1\dots (s-1)r+1} $

If you want an increasing sequence you can't take two of the same color, if you want a decreasing sequence you can't take two of different colors.


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.