# Forcing empty convex polygons

Let us call a convex polygon $$P$$ formed from the points of a set $$X$$ empty if the interior of $$P$$ contains no point of $$X$$. Erdös suggested the following variation.

For each $$n$$, let $$g^*(n)$$ denote the least integer such that any set of $$g^*(n)$$ points in the plane in general position must always contain the vertices of an empty convex $$n$$-gon. This is a slight variation of $$g(n)$$ of Erdös and Szekeres.

# Problem

Is it true that $$g^*(n)$$ always exists, and if it does, determine or estimate $$g^*(n)$$.

It is easy to show that $$g^*(3)=3$$ and $$g^*(4)=5$$.

Harborth [4] showed that $$g^*(5)=10$$.

Horton [5] constructed an infinite set of points with no empty convex 7-gon, implying that $$g^*(7)= \infty$$.

Overmars [8] used a computer to find a set of 29 points without an empty convex hexagon. This proved $$g^*(6) \ge 30$$.

Gerken [3] proved that $$g^*(6)$$ is finite. By case analysis, he showed that any set with a convex 9-gon must contain an empty hexagon. Using the function $$g(n)$$ from the Erdös Szekeres theorem, this means that $$g^*(6) \le g(9)$$, which is known to be between 129 and 1717. Nicolas [7] independently proved that $$g^*(6)$$ is finite, bounding it by $$g(25)$$.

Koshelev [6] further showed that $$g^*(6) \le \max\{g(8), 400\}$$, which gives the current upper bound of 463.

A weaker restriction in this vein has been considered by Bialostocki, Dierker and Voxman [1]. They prove that there is a function $$E(n,q)$$ such that if $$X$$ is a subset of the plane in general position with $$\vert X\vert \geq E(n,q)$$, then $$X$$ always contains the vertices of a convex $$n$$-gon with $$tq$$ points of $$X$$ in its interior for some integer $$t$$, where $$n \geq q+2$$. Caro [2] shows that one can always take $$E(n,q) \leq 2^{c(q)n}$$ where $$c(q)$$ depends only on $$q$$.

Bibliography
1 A. Bialostocki, P. Dierker and W. Voxman, Some notes on the Erdös-Szekeres theorem, Discrete Math. 91 (1991), 117-127.

2 Y. Caro, On the generalized Erdös-Szekeres Conjecture- a new upper bound, Discrete Math. 160 (1996), 229-233.

3 T. Gerken, On empty convex hexagons in planar point set,'' Discrete Comput. Geom., 39, 239–272 (2008).

4 H. Harborth, Konvexe Fünfecke in ebenen Punktmengen, Elem. Math. 33 (1978), 116-118.

5 J. D. Horton, Sets with no empty convex $$7$$-gons, Canad. Math. Bull. 26, (1983), 482-484.

6 V. A. Koshelev, On the Erdös-Szekeres problem,'' Doklady Mathematics, 76, No. 1, 603-605 (2007)

7 C. Nicolas, The empty hexagon theorem,'' Discrete Comput. Geom., 38, No. 2, 389–397 (2007).

8 M. Overmars, Finding sets of points without empty convex 6-gons,'' Discrete Comput. Geom., 29, 153–158 (2003).