Minimum number of empty convex hexagons in an $n$-point set: bound $h_6(n)$
Statement
Let $S$ be a set of $n$ points in general position in the plane (no three collinear). A $6$-hole of $S$ is a subset of six points in convex position whose convex hull contains no other point of $S$. Let $h_6(n)$ be the minimum, over all $n$-point sets, of the number of $6$-holes. Determine the asymptotic growth of $h_6(n)$; the known lower and upper bounds currently match in neither constant nor exponent.
Acceptance. ADVANCES: (i) exact values of $h_6(n)$ for new small $n$, each with the extremal configuration and an exhaustive/SAT verification; or (ii) an improved asymptotic lower bound (better constant or super-linear exponent) with proof; or (iii) an improved upper-bound construction (constant below $0.2005$) with an explicit point-set family. FULLY RESOLVES: matching bounds fixing the asymptotic order and constant of $h_6(n)$. Provide configurations plus a verification script.
Background
Existence is settled: every sufficiently large point set contains a $6$-hole (Gerken; Nicolás, ~2007), and the exact threshold is now known — every set of $30$ points in general position has an empty convex hexagon, while a $29$-point set without one exists (Heule–Scheucher, 'Happy Ending: An Empty Hexagon in Every Set of 30 Points', 2024, SAT-based). The COUNTING/minimization question $h_6(n)$ remains open: explicit constructions give $O(n^2)$ $6$-holes (upper bound on the minimum $\approx 0.2005\,n^2 + o(n^2)$), while the best general lower bound is only roughly linear (on the order of $n/463$), so neither the constant nor even the exponent is pinned. The $5$-hole minimum $h_5(n)$ has the same matching-bounds gap. Related: bounds on the maximum number of $k$-holes with no $(k{+}1)$-hole (arXiv:2606.05721, 2026). An attacker must bring: a SAT / order-type enumerator (as used for the existence threshold) to compute exact $h_6(n)$ for small $n$, then a construction-generalizer to conjecture the asymptotic constant, matched by a discharging / counting lower-bound argument. Exact small-$n$ minima are finite checkable certificates; improving either bound's constant/exponent is publishable.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | On empty pentagons and hexagons in planar point sets | arxiv |
| REF-02 | Heule & Scheucher, Happy Ending: An Empty Hexagon in Every Set of 30 Points (2024) | paper |
| REF-03 | On the maximum number of k-holes in point sets with no (k+1)-hole (2026) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.