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