Home » Subject » Geometry

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
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.

Here an 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.

Related problems

Big Line or Big Clique in Planar Point Sets
Erdös-Szekeres conjecture

Bibliography

[G] Tobias Gerken. Empty Convex Hexagons in Planar Point Sets, Discrete Comput Geom (2008) 39:239–272, MathSciNet

[N] Carlos M. Nicolas. The Empty Hexagon Theorem, Discrete Comput Geom 38:389–397 (2007), MathSciNet.

[V] Pavel Valtr, 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.
add new comment