4
$\begingroup$

In this math.stackexchange question Adam Rubinson asked (I paraphrase):

Given a natural number $r$, what is the least number $n$ such that every strictly increasing sequence of $n$ real numbers has a subsequence $x_1,x_2,\dots,x_r$ of length $r$ whose sequence of differences $x_2-x_1,x_3-x_2,\dots,x_r-x_{r-1}$ is (nonstrictly) monotonic? (E.g., if $r=4$ then $n=7$.)

I can't recall having seen this before, but it seems like a reasonably natural question, so it must be discussed somewhere in the literature. Where?

Edit. I'm not sure the question should be closed as a duplicate, seeing as I posted it as a reference request, and I still don't know where or whether this result appears as a traditional publication.

I would have expected this to be a "classical" problem. It's hard to believe that it's not among the thousands of problems Paul Erdős wrote about.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ mathoverflow.net/questions/90128/… . Note that the "increasing" condition does not change anything, since you can always add an arithmetic sequence with sufficiently high difference to your sequence, which will make it increasing. $\endgroup$
    – darij grinberg
    Commented Apr 4, 2023 at 23:15
  • 5
    $\begingroup$ Does this answer your question? Erdős-Szekeres for first differences $\endgroup$
    – darij grinberg
    Commented Apr 4, 2023 at 23:17
  • 2
    $\begingroup$ The MO question linked by Darij has a hidden/deleted answer by Gjergji Zaimi which does not solve this problem but indicates that the same answer appears in a similar problem about sequences of points in general position on the plane containing either an "$l$-cap" or a "$k$-cup" (natural notions expressed using slopes computed via differences of coordinates), and that problem is solved in the original paper of Erdős–Szekeres (numdam.org/item/?id=CM_1935__2__463_0). Probably you just have to do a careful search through lemmas and propositions of papers that cite Erdős–Szekeres... $\endgroup$
    – Vladimir Dotsenko
    Commented Apr 5, 2023 at 5:21
  • 1
    $\begingroup$ @darijgrinberg No doubt I'm just being stupid, but I don't see why restricting to increasing sequences does not change anything. If I add an arithmetic sequence, then the new sequence will be convex (concave) iff the original sequence was convex (concave), but it is not so for subsequences. $\endgroup$
    – bof
    Commented Apr 6, 2023 at 10:00
  • 2
    $\begingroup$ @VladimirDotsenko Actually that old Erdős–Szekeres paper seems to be the reference I was looking for. Thank you! $\endgroup$
    – bof
    Commented Apr 8, 2023 at 7:45

1 Answer 1

Reset to default
2
$\begingroup$

As pointed out in a comment by Vladimir Dotsenko, the problem I asked about was posed and solved in the classical paper by Erdős and Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470 (pdf); see the discussion beginning with "We solve now a similar problem" on p. 468.

In another comment Darij Grinberg pointed out that a generalization to possibly non-monotonic sequences was the subject of a 2012 math overflow question by Seva which was answered by Sergey Norin.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .