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

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}.

In , 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}} 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}} 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 , 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!

 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.

 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.

• You can have at most three points in a plane in "general position". To get a fourth point, you have to leave the plane. Thus your entire assertion requires that $n =1$ or $n = 2$. Aug 25, 2022 at 11:03
• @PaulSinclair in this context, "general position" means that there are not more than two points in the same line. I have edited the OP to make it clearer. Thanks for your observation! Aug 25, 2022 at 15:15

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.