Problem 216

Let $g(k)$ be the smallest integer (if any such exists) such that any $g(k)$ points in $\mathbb{R}^2$ contains an empty convex $k$ -gon (i.e. with no point in the interior). Does $g(k)$ exist? If so, estimate $g(k)$ .

Source: erdosproblems.com/216

Geometry
Convexity

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved: the site labels the problem disproved on Horton's construction of arbitrarily large point sets with no empty convex heptagon, recorded on the Horton claim page (1983). The site's remarks credit the instances that exist: $g(4)=5$ (Erdős, no source given, so it stays in prose), $g(5)=10$ on the Harborth claim page (1978), the existence of $g(6)$ on the Nicolás and Gerken claim pages, and $g(6)=30$ on the Heule–Scheucher claim page (2024).

Ge08: Gerken, Tobias, Empty convex hexagons in planar point sets. Discrete Comput. Geom. (2008), 239-272.
Ha78: Harborth, Heiko, Konvexe Fünfecke in ebenen Punktmengen. Elem. Math. (1978), 116-118.
HeSc24: M. Heule and M. Scheucher, Happy Ending: An Empty Hexagon in Every Set of $30$ Points. Tools and Algorithms for the Construction and Analysis of Systems, Lecture Notes in Computer Science (2024), 61-80.
Ho83: Horton, J. D., Sets with no empty convex 7-gons. Canad. Math. Bull. (1983), 482-484.
Ni07: Nicolás, Carlos M., The empty hexagon theorem. Discrete Comput. Geom. (2007), 389-397.

Problem 216

Status

Proof claims

Discussion