Lower bound on the number of points in general position in the plane guaranteeing an n-cup or n-cap

Question

Consider some set $X$ of $(n-1)^2+2$ points in general position in the plane. We can introduce a coordinate system $\left(x,y\right)$ in the plane, such that $X=\left\{ \left(x_{1},y_{1}\right),\left(x_{2},y_{2}\right),...,\left(x_{(n-1)^2+2},y_{(n-1)^2+2}\right)\right\}$, with $x_{i}\neq x_{j}\space \forall i,j$ and $x_{1}<x_{2}<\dots<x_{(n-1)^2+2}$.

In [1], a subset of points $\left\{\left(x_{i_{1}},y_{i_{1}}\right),\left(x_{i_{2}},y_{i_{2}}\right),...,\left(x_{i_{r}},y_{i_{r}}\right)\right\}$ is called an r-cup if $x_{i_{1}}<x_{i_{2}}<\dots<x_{i_{r}}$ and $\frac{y_{i_{1}}-y_{i_{2}}}{x_{i_{1}}-x_{i_{2}}}<\frac{y_{i_{2}}-y_{i_{3}}}{x_{i_{2}}-x_{i_{3}}}<...<\frac{y_{i_{r-1}}-y_{i_{r}}}{x_{i_{r-1}}-x_{i_{r}}}$, and an r-cap if $x_{i_{1}}<x_{i_{2}}<...<x_{i_{r}}$ and $\frac{y_{i_{1}}-y_{i_{2}}}{x_{i_{1}}-x_{i_{2}}}>\frac{y_{i_{2}}-y_{i_{3}}}{x_{i_{2}}-x_{i_{3}}}>...>\frac{y_{i_{r-1}}-y_{i_{r}}}{x_{i_{r-1}}-x_{i_{r}}}$.

Other hand, Erdös-Szekeres Theorem asserts that, given $r, s$, any sequence of distinct real numbers with length at least $(r − 1)(s − 1) + 1$ contains a monotonically increasing subsequence of length $r$ or a monotonically decreasing subsequence of length $s$.

Let us consider the set $$S=\{\frac{y_{1}-y_{2}}{x_{1}-x_{2}},\frac{y_{2}-y_{3}}{x_{2}-x_{3}},\dots,\frac{y_{(n-1)^2+1}-y_{(n-1)^2+2}}{x_{(n-1)^2+1}-x_{(n-1)^2+2}}\}$$

Erdös-Szekeres Theorem guarantees the existence of a monotonically increasing or decreasing subsequence of length $n$ in the sequence formed with the elements of $S$. Thus , $(n-1)^2+2$ points in general position guarantee the existence of some n-cup or n-cap.

However, in [2], Erdös and Szekeres construct a set of $2^{n-2}$ points in general position in the plane that does not have neither an n-cup nor n-cap, and $2^{n-2}> (n-1)^2+2 \space \forall n>7 $, so I believe the proof exposed should be flawed. However, I do not find the mistake, so if someone could point it out it would be welcomed.

Thanks!

[1] Chung, F. R. K.; Graham, R. L., Forced convex (n)-gons in the plane, Discrete Comput. Geom. 19, No. 3, 367-371 (1998). ZBL0908.52004.

[2] Erdős, Pál; Szekeres, George, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 3-4, 53-62 (1961). ZBL0103.15502.

Answer 1

Let us consider the set $$S=\{\frac{y_{1}-y_{2}}{x_{1}-x_{2}},\frac{y_{2}-y_{3}}{x_{2}-x_{3}},\dots,\frac{y_{(n-1)^2+1}-y_{(n-1)^2+2}}{x_{(n-1)^2+1}-x_{(n-1)^2+2}}\}$$

Erdös-Szekeres Theorem guarantees the existence of a monotonically increasing or decreasing subsequence of length $n$ in the sequence formed with the elements of $S$. Thus , $(n-1)^2+2$ points in general position guarantee the existence of some n-cup or n-cap.

No it does not. To have an $n$-cup or $n$-cap, you pick $n$ points $(x_i, y_i)$. In your argument you are picking $n$ slopes instead. To see the difference, suppose your $n$ slopes start with $\dfrac{y_1 - y_2}{x_1 - x_2},\dfrac{y_3 - y_4}{x_3 - x_4},\dots$. What points are you picking for your $n$-cap or cup? To get the slopes you've chosen, you need all four of $(x_1,y_1)$ to $(x_4,y_4)$. But that means you are also getting the slope $\dfrac{y_2 - y_3}{x_2 - x_3}$, which was not among your selections, presumably because it doesn't fit the needed ordering.