Erdős Problem #107

Erdős Problem 107: convex polygons

Statement and scope

This revises the earlier GPT-5.2 attempts. Their proposed small-case proofs used invalid implications concerning empty triangles or triangulation edges. The arguments below replace those steps. The cup--cap method is classical Erdős--Szekeres mathematics, not a new result. Current statement and historical references: https://www.erdosproblems.com/107.

A complete cup--cap recurrence

Let $M(a,b)$ be the largest number of points having neither an $a$-cup nor a $b$-cap. For $a,b\ge2$, \[ M(a,b)\le {a+b-4\choose a-2}. \tag{1} \] The boundary values $M(2,b)=M(a,2)=1$ follow because any two points constitute both a cup and a cap. For $a,b\ge3$, partition a counterexample into $A$, the points which end an $(a-1)$-cup, and its complement $B$. The set $B$ has neither an $(a-1)$-cup nor a $b$-cap.

The set $A$ has no $(b-1)$-cap. Indeed, suppose $q_1,\ldots,q_{b-1}$ were one. Choose an $(a-1)$-cup ending at $q_1$, with penultimate point $p$. If the slope $pq_1$ is smaller than the slope $q_1q_2$, appending $q_2$ produces an $a$-cup. If it is larger, prepending $p$ produces a $b$-cap. Equality would make $p,q_1,q_2$ collinear. All alternatives are impossible. Thus \[ |A|\le M(a,b-1),\qquad |B|\le M(a-1,b). \] Induction and Pascal's identity prove $1$, including finiteness of the maxima. Taking $a=b=n$ gives \[ f(n)\le {2n-4\choose n-2}+1. \tag{2} \]

The exact four-point case

In the four-point set $\{B,C,D,E\}$, the line $DE$ is a supporting line, and the line $BC$ is also a supporting line because $D,E$ lie inside $ABC$. General position makes both $DE$ and $BC$ edges of this four-point convex hull, with four different endpoints. Hence all four points are vertices, proving $f(4)=5$.

Remaining gap

COMPLETION ESTIMATE

Erdős Problem #107

1) FORMAL RESTATEMENT

The conjectured exact value is \[ f(n)=2^{n-2}+1\quad(n\ge3). \]

2) QUICK LITERATURE/CONTEXT CHECK

• Erdős--Szekeres proved the bounds $2^{n-2}+1\le f(n)\le \binom{2n-4}{n-2}+1$.
• Several improvements exist; the best stated bound is $f(n)\le 2^{n+O(\sqrt{n\log n})}$.

3) ATTACK PLAN

• Proof track (full conjecture): show every set of $2^{n-2}+1$ points contains a convex $n$-gon, likely via a sharp recursion or a refined partial-order argument.
• Disproof track: exhibit, for some $n$, a configuration of $2^{n-2}+1$ points with no convex $n$-gon.

4) WORK

Lemma 107.1 (the case $n=4$: $f(4)=5$).

Proof. Lower bound $f(4)\ge5$. There exists a $4$-point set with no convex quadrilateral: take three vertices of a triangle and a fourth point strictly inside that triangle. Any four-point subset is the whole set, and one point lies in the convex hull of the other three, so there is no convex $4$-gon. Thus $f(4)\ge5$.

Upper bound $f(4)\le5$. Let $P$ be any set of $5$ points with no three collinear. Consider all triangles formed by triples of points in $P$, and choose a triangle $\triangle ABC$ of minimum (Euclidean) area.

Claim: no other point of $P$ lies strictly inside $\triangle ABC$. Indeed, if some point $D\in P$ lies inside $\triangle ABC$, then the three triangles $\triangle ABD$, $\triangle BCD$, $\triangle CAD$ form a partition of $\triangle ABC$ into three nondegenerate triangles. In particular, each of these triangles has area strictly smaller than $\triangle ABC$, contradicting the minimality of $\triangle ABC$.

Therefore, the remaining two points of $P\setminus\{A,B,C\}$ lie outside the triangle $\triangle ABC$. Hence the convex hull $\operatorname{conv}(P)$ cannot be a triangle (a triangular convex hull would contain all points in or on that triangle, with at least two points inside, contradicting the claim). Thus $\operatorname{conv}(P)$ has at least $4$ vertices, and those $4$ vertices form a convex quadrilateral.

So every $5$-point set contains a convex $4$-gon, i.e. $f(4)\le5$. Together with the lower bound, $f(4)=5$. $\square$

Lemma 107.2 (monotonicity and trivial bounds).

1. $f(n+1)\ge f(n)$.
2. $f(n)\ge n$.

Proof. $2$ is immediate since fewer than $n$ points cannot contain $n$ points in convex position.

For $1$: by definition, any set of $f(n+1)$ points in general position contains $n+1$ points in convex position. Removing any one of these $n+1$ vertices leaves $n$ points still in convex position. Hence any set of $f(n+1)$ points contains a convex $n$-gon, so $f(n)\le f(n+1)$, i.e. $f(n+1)\ge f(n)$. $\square$

5) VERIFICATION (FAST REALITY CHECK)

• $f(3)=3$: any $3$ noncollinear points form a triangle.
• Lemma 107.1 gives $f(4)=5$.
• The conjecture predicts $f(5)=2^{3}+1=9$, consistent with the statement in the problem text that Turán and Makai proved $f(5)=9$.

6) FINAL

(i) Strongest fully proved partial result obtained here. A complete proof that $f(4)=5$ (Lemma 107.1), plus basic monotonicity/trivial bounds (Lemma 107.2).

(ii) Exact first gap. Proving (or disproving) the general identity $f(n)=2^{n-2}+1$ for all $n\ge3$.

(iii) Top 3 next moves (concrete targets).

1. Re-prove the general Erdős--Szekeres upper bound $f(n)\le \binom{2n-4}{n-2}+1$ in a fully self-contained way as a stepping stone.
2. Attempt to sharpen the induction/recursion to match the lower bound $2^{n-2}+1$.
3. Computationally search for extremal configurations for $n=6,7$ to test structure and potential stability.

(iv) Minimal counterexample structure. A disproof would require some $n$ and an explicit set of $2^{n-2}+1$ points in general position containing no convex $n$-gon; it would have to beat the classical Erdős--Szekeres construction of size $2^{n-2}$ without creating a convex $n$-tuple.

OUTPUT 1) FORMAL RESTATEMENT Definitions/Conventions. - A finite set $P\subset\mathbb R^2$ is in general position if no three points are collinear. - For $n\ge 3$, a subset $Q\subseteq P$ of size $n$ forms the vertices of a convex $n$-gon if the $n$ points of $Q$ are in convex position, i.e. every point of $Q$ is a vertex of $\mathrm{conv}(Q)$. - Define $f(n)$ to be the least integer $N$ such that every set $P\subset\mathbb R^2$ of $N$ points in general position contains an $n$-point subset in convex position.

Conjecture (Erdős--Szekeres). Prove that for all $n\ge 3$, \[f(n)=2^{n-2}+1.\]

2) QUICK LITERATURE/CONTEXT CHECK Web browsing is not available in this session. From the problem statement: - The exact values $f(4)=5$ and $f(5)=9$ are known. - Erdős--Szekeres proved $2^{n-2}+1\le f(n)\le \binom{2n-4}{n-2}+1$. - Stronger upper bounds are known, but the exact formula is open in general. I do not use the deep upper bounds here.

3) ATTACK PLAN Proof track ideas: 1. Try to prove the conjectured exact formula by understanding extremal configurations with no convex $n$-gon and showing they have size at most $2^{n-2}$. 2. For small $n$, prove exact values directly as a reality check and as a base for any induction attempt.

Disproof track ideas: 1. Try to construct, for some $n$, a set of size $2^{n-2}+1$ in general position with no convex $n$-gon. Any such construction would refute the conjecture.

Chosen path in this attempt: prove two basic, fully rigorous facts: monotonicity of $f(n)$, and the exact value $f(4)=5$ (the first nontrivial case).

4) WORK Lemma 1 (Monotonicity). For all $n\ge 3$, one has $f(n+1)\ge f(n)$.

Proof. Let $N:=f(n+1)$. By definition, every set of $N$ points in general position contains a subset of $n+1$ points in convex position. Any subset of vertices of a convex polygon is again in convex position (because removing vertices cannot create an interior point among the remaining ones). Therefore, the same $N$ points also contain $n$ points in convex position. Thus $N$ is admissible for $f(n)$, so $f(n)\le N=f(n+1)$. $\square$

Lemma 2 (Exact value $f(4)=5$). Every set of $5$ points in $\mathbb R^2$ in general position contains $4$ points in convex position, and there exists a set of $4$ points in general position with no $4$ points in convex position. Hence $f(4)=5$.

Proof. Lower bound $f(4)\ge 5$: take three noncollinear points $A,B,C$ and a fourth point $D$ strictly inside the triangle $\triangle ABC$. Then $A,B,C,D$ are in general position, but $D$ is not a vertex of the convex hull of $\{A,B,C,D\}$, so these four points are not in convex position. Thus $f(4)>4$, i.e. $f(4)\ge 5$.

Upper bound $f(4)\le 5$: let $P$ be any set of $5$ points in general position. If at least $4$ points of $P$ lie on the boundary of $\mathrm{conv}(P)$, then those $4$ boundary points are in convex position and we are done. So assume $\mathrm{conv}(P)$ has at most $3$ vertices, meaning at least one point of $P$ lies strictly inside the convex hull of the others.

Consider any straight-line triangulation of the point set $P$ (a planar subdivision of $\mathrm{conv}(P)$ into triangles whose vertices are points of $P$ and whose edges are noncrossing segments between points of $P$). Such a triangulation exists for any finite set of points in general position. Because $P$ is not all on the boundary of its convex hull, the triangulation has at least one interior edge $ab$ (an edge not on the boundary of $\mathrm{conv}(P)$). This interior edge is incident to exactly two triangles in the triangulation, say triangles $abc$ and $abd$ with $c\ne d$.

Since $ab$ is an interior edge, the triangles $abc$ and $abd$ lie on opposite sides of the line through $a$ and $b$. Equivalently, the points $c$ and $d$ lie in opposite open half-planes determined by the line $ab$. In particular, the segment $\overline{cd}$ intersects the segment $\overline{ab}$ at an interior point of both segments. Whenever two segments $\overline{ab}$ and $\overline{cd}$ cross (and no three of $a,b,c,d$ are collinear), the four endpoints $a,b,c,d$ are in convex position: they are the vertices of a convex quadrilateral with diagonals $\overline{ab}$ and $\overline{cd}$. Thus $\{a,b,c,d\}\subseteq P$ is a 4-point subset in convex position.

This proves every $5$-point general-position set contains a convex quadrilateral, i.e. $f(4)\le 5$.

Combining both bounds yields $f(4)=5$. $\square$

FAST REALITY CHECK - The conjectured formula gives $f(3)=2^{1}+1=3$ and $f(4)=2^{2}+1=5$, matching the trivial triangle case and Lemma 2. - The statement reports $f(5)=2^{3}+1=9$, consistent with the conjecture but not proved here.

5) VERIFICATION - Lemma 1 uses only the fact that subsets of vertices of a convex polygon remain in convex position. - In Lemma 2, the key geometric step is: if a line through two interior points intersects two sides of a triangle, then two triangle vertices lie on opposite sides of that line; then crossing diagonals imply convex position of four points. No collinearity assumptions ensure the crossing criterion is valid.

6) FINAL UNRESOLVED

(i) Strongest fully proved partial result: I proved monotonicity of $f(n)$ (Lemma 1) and established the exact value $f(4)=5$ with a complete proof (Lemma 2).

(ii) First gap: Prove $f(n)\le 2^{n-2}+1$ for general $n$ (or find a counterexample for some $n$). Beyond $n=5$, known proofs require substantially deeper combinatorial geometry than the small-case argument in Lemma 2.

(iii) Top 3 next moves (concrete): 1. Prove the next open-looking case(s) directly (e.g. re-derive $f(5)=9$) as a stepping stone and to understand extremal configurations. 2. Study the structure of known lower-bound constructions of size $2^{n-2}$ with no convex $n$-gon (as mentioned in the statement) and attempt to show they are extremal. 3. Try to connect the conjecture to an induction on $n$ by identifying a canonical "splitting vertex" in a point set that reduces the problem to smaller $n$.

(iv) What a minimal counterexample would likely look like (structure/parameters): For some $n\ge 6$, a set of $2^{n-2}+1$ points in general position with no $n$ points in convex position; such a configuration would have to be highly structured and likely resemble known extremal constructions for smaller $n$.