TY - JOUR
T1 - A superlinear lower bound on the number of 5-holes
AU - Aichholzer, Oswin
AU - Balko, Martin
AU - Hackl, Thomas
AU - Kyncl, Jan
AU - Parada, Irene
AU - Scheucher, Manfred
AU - Valtr, Pavel
AU - Vogtenhuber, Birgit
PY - 2020/7
Y1 - 2020/7
N2 - Let P be a finite set of points in the plane in general position, that is, no three points of P are on a common line. We say that a set H of five points from P is a 5-hole in P if H is the vertex set of a convex 5-gon containing no other points of P. For a positive integer n, let h
5(n) be the minimum number of 5-holes among all sets of n points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for h
5(n) have been of order Ω(n) and O(n
2), respectively. We show that h
5(n)=Ω(nlog
4/5n), obtaining the first superlinear lower bound on h
5(n). The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set P of points in the plane in general position is partitioned by a line ℓ into two subsets, each of size at least 5 and not in convex position, then ℓ intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.
AB - Let P be a finite set of points in the plane in general position, that is, no three points of P are on a common line. We say that a set H of five points from P is a 5-hole in P if H is the vertex set of a convex 5-gon containing no other points of P. For a positive integer n, let h
5(n) be the minimum number of 5-holes among all sets of n points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for h
5(n) have been of order Ω(n) and O(n
2), respectively. We show that h
5(n)=Ω(nlog
4/5n), obtaining the first superlinear lower bound on h
5(n). The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set P of points in the plane in general position is partitioned by a line ℓ into two subsets, each of size at least 5 and not in convex position, then ℓ intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.
KW - Empty k-gon
KW - Empty pentagon
KW - Erdös–Szekeres type problem
KW - Planar point set
KW - k-Hole
UR - http://www.scopus.com/inward/record.url?scp=85079878658&partnerID=8YFLogxK
U2 - 10.1016/J.JCTA.2020.105236
DO - 10.1016/J.JCTA.2020.105236
M3 - Article
SN - 0097-3165
VL - 173
JO - Journal of Combinatorial Theory, Series A
JF - Journal of Combinatorial Theory, Series A
M1 - 105236
ER -