Generalised Empty Hexagon Conjecture

Importance: Medium ✭✭
Author(s): Wood, David R.
Subject: Geometry
Keywords: empty hexagon
Recomm. for undergrads: yes
Posted by: David Wood
on: March 26th, 2014

\begin{conjecture} For each $\ell\geq3$ there is an integer $f(\ell)$ such that every set of at least $f(\ell)$ points in the plane contains $\ell$ collinear points or an empty hexagon. \end{conjecture}

Here an \emph{empty hexagon} in a set of points $P$ consists of a subset $S\subseteq P$ of six points in convex position with no other point in $P$ in the convex hull of $S$. The $\ell=3$ case of the conjecture (that is, for point sets in general position) was an outstanding open problem for many years, until its solution by Gerken [G] and Nicolas [N]. Valtr [V] found a simple proof.


[G] Tobias Gerken. \href[Empty Convex Hexagons in Planar Point Sets]{}, Discrete Comput Geom (2008) 39:239–272, \MRhref{MR2383761}

[N] Carlos M. Nicolas. \href[The Empty Hexagon Theorem]{}, Discrete Comput Geom 38:389–397 (2007), \MRhref{2343313}.

[V] Pavel Valtr, \href[On Empty Hexagons]{}, in: J. E. Goodman, J. Pach, and R. Pollack, Surveys on Discrete and Computational Geometry, Twenty Years Later, Contemp. Math. 453, AMS, 2008, pp. 433-441.

* indicates original appearance(s) of problem.