Problem 107

Let $f(n)$ be minimal such that any $f(n)$ points in $\mathbb{R}^2$ , no three on a line, contain $n$ points which form the vertices of a convex $n$ -gon. Prove that $f(n)=2^{n-2}+1$ .

Source: erdosproblems.com/107

Geometry
Convexity

Wiki page

Status

Open

No claim settles this problem.

Falsifiable. The frontmatter standing is derived from the claim pages under claims/: three accepted partial claims settle instances of the conjectured equality and its lower half (Klein's $f(4)=5$ as published by Erdős and Szekeres, the Erdős--Szekeres construction giving $f(n)\ge2^{n-2}+1$ , and Szekeres and Peters's $f(6)=17$ ; see the Current assessment), and no claim addresses the conjecture for every $n$ , so the problem stays open.

Er97e: Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. (1997), 527-537.
ErSz35: Erdős, P. and Szekeres, G., A combinatorial problem in geometry. Compos. Math. (1935), 463-470.
ErSz60: Erdős, P. and Szekeres, G., On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. (1960/61), 53-62.
Gr04: Green, Ben, The Cameron-Erdős conjecture. Bull. London Math. Soc. (2004), 769-778. The site's commentary cites [Gr04] for Graham's offer of a prize for a proof, but the site's reference record resolves the key to this paper of Green on sum-free sets, the entry it shares with Problem 748, which does not concern this problem; the publication of Graham that the commentary describes is not identified on this page.
HMPT20: Holmsen, Andreas F. and Mojarrad, Hossein Nassajian and Pach, János and Tardos, Gábor, Two extensions of the Erdős-Szekeres problem. J. Eur. Math. Soc. (JEMS) (2020), 3981-3995.
Su17: Suk, Andrew, On the Erdős-Szekeres convex polygon problem. J. Amer. Math. Soc. (2017), 1047-1053.
SzPe06: Szekeres, George and Peters, Lindsay, Computer solution to the 17-point Erdős-Szekeres problem. ANZIAM J. 48 (2006), 151-164. Not among the site's references.

Problem 107

Status

Proof claims

Discussion