The Happy Ending Problem

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite set $P\subset\mathbb R^2$ is in general position if no three of its points are collinear. A subset $Q\subset P$ is in convex position if every point of $Q$ is a vertex of its convex hull. For $n\geq3$, let $g(n)$ be the least positive integer $N$ such that every general-position set $P\subset\mathbb R^2$ with $|P|=N$ contains a convex-position subset $Q\subset P$ with $|Q|=n$. The Erdős--Szekeres theorem ensures that this minimum is finite.

Statement recorded in the supplied source.

Determine $g(n)$ for every integer $n\geq3$. In particular, is \[ g(n)=2^{n-2}+1\qquad\text{for every }n\geq3? \] [S2]

Short English statement

How many points in general position guarantee a convex polygon with a prescribed number of vertices? Is the minimum always one more than the standard power-of-two lower bound?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1214 (GEO-023). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Andrew Suk, On the Erdős--Szekeres convex polygon problem, arXiv:1604.08657v2 (2016), Section 1 and footnote 1. https://arxiv.org/pdf/1604.08657.