Overview
This study focuses on determining the maximum number of $k$-holes in planar point sets under the constraint that these sets do not contain a $(k+1)$-hole. A $k$-hole refers to an empty convex $k$-gon formed by points from the set. The research specifically addresses point sets in general position within the plane and of size at most $n$.
Research Context
The investigation is rooted in the classical problem posed by Erd\H{o}s, which seeks the minimum number of empty convex $k$-gons determined by an $n$-element point set in the plane. A foundational result in this area is the empty hexagon theorem, independently established by Gerken and Nicol\'as. This theorem indicates that any sufficiently large planar point set must contain a $6$-hole. Conversely, Horton's construction provides an example of arbitrarily large point sets that do not contain a $7$-hole. The current work initiates the study of a related but distinct problem: the maximum possible number of $k$-holes in point sets specifically constructed to lack a $(k+1)$-hole.
Approach
The research defines $h_k(n)$ as the maximum number of $k$-holes observable in a planar point set. This set is characterized by being in general position, having a size of at most $n$, and crucially, containing no $(k+1)$-hole. The study aims to establish bounds for $h_k(n)$ for fixed values of $k \geq 6$.
Findings
For each fixed $k \geq 6$, the researchers established both lower and upper bounds for $h_k(n)$, the maximum number of $k$-holes in a planar point set of size at most $n$ with no $(k+1)$-hole. Specifically, the findings indicate the existence of absolute constants $c_1, c_2 > 0$ such that the following inequality holds:
$ (c_1/k)^{\lfloor k/3\rfloor} n^{\lfloor k/3\rfloor} \leq h_k(n) \leq (c_2/k)^{\lceil k/2\rceil} n^{\lceil k/2\rceil} $
This inequality provides a quantitative range for $h_k(n)$ based on the set size $n$ and the value of $k$. The specific exponents $\lfloor k/3\rfloor$ and $\lceil k/2\rceil$ in the bounds highlight the relationship between the number of $k$-holes and the absence of $(k+1)$-holes.
Why This Matters
This research contributes to the understanding of geometric properties of point sets, particularly concerning the distribution and existence of empty convex polygons. The established bounds for $h_k(n)$ provide specific quantitative insights into a problem derived from classical combinatorial geometry. By characterizing the maximum number of $k$-holes under the restriction of no $(k+1)$-hole, the study sheds light on structural constraints within planar point sets.