On the maximum number of $k$-holes in point sets with no $(k+1)$-hole

Abstract

The classical problem of Erdős asks for the minimum number of empty convex $k$-gons determined by an $n$-element point set in the plane. The celebrated empty hexagon theorem, proved independently by Gerken and Nicolás, shows that every sufficiently large planar point set contains a $6$-hole, while Horton's famous construction shows the existence of arbitrarily large point sets with no $7$-hole. In this paper, we initiate the study of the maximum number of $k$-holes in planar point sets with no $(k+1)$-hole. More precisely, for each fixed $k\ge 6$, let $h_k(n)$ be the maximum number of $k$-holes determined by a planar point set in general position, of size at most $n$, and with no $(k+1)$-hole. We prove that there are absolute constants $c_1,c_2>0$ such that $(c_1/k{)}^{\lfloor k/3\rfloor }{n}^{\lfloor k/3\rfloor }\le h_k(n)\le (c_2/k{)}^{\lceil k/2\rceil }{n}^{\lceil k/2\rceil }$.

9 pages, 3 figures