Forcing empty convex polygons
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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 7gon, 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 9gon 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ösSzekeres theorem,
Discrete Math.
91 (1991), 117127.

2 
Y. Caro, On the generalized ErdösSzekeres Conjecture a new upper
bound,
Discrete Math. 160 (1996), 229233.

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), 116118.

5 
J. D. Horton,
Sets with no empty convex \( 7\)gons,
Canad. Math. Bull. 26, (1983), 482484.

6  V. A. Koshelev, ``On the ErdösSzekeres problem,''
Doklady Mathematics, 76, No. 1, 603605 (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 6gons,''
Discrete Comput. Geom., 29, 153–158 (2003).
