A superlinear lower bound on the number of 5-holes
Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kynčl, Irene Parada, Manfred Scheucher, Pável Valtr, Birgit Vogtenhuber · Journal of Combinatorial Theory Series A · 2020
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 ) = Ω ( n log 4 / 5 n ) , 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.