pith. sign in

arxiv: 2606.08762 · v1 · pith:VXKOGQ4Lnew · submitted 2026-06-07 · 🧮 math.CO

Many holes but no large one: maximizing k-holes while forbidding (k+1)-holes

Martin Andri\v{c}\'ik , Alica Dom\'anyov\'a , Adam D\v{z}avoronok , Aleksa D\v{z}uklevski , Matou\v{s} \v{S}afr\'anek This is my paper

Pith reviewed 2026-06-27 18:06 UTC · model grok-4.3

classification 🧮 math.CO
keywords empty convex k-gonsk-holespoint sets in general positionno (k+1)-holesextremal combinatorial geometryconvex polygons in the plane
0
0 comments X

The pith

Point sets without any empty (k+1)-gon contain at most 2 to the power of (n minus k) empty k-gons when n minus k is small.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper determines the exact maximum number of empty convex k-gons possible in an n-point set in the plane that has no empty convex (k+1)-gon. When n equals k plus a small integer a at most k over 2 minus 1, this maximum equals exactly 2 to the power a. The result gives a precise count in the regime of few extra points beyond k, showing how the no-(k+1)-hole condition sharply limits the count of k-holes. The authors also identify the point configurations that achieve this number. Additional bounds are derived for cases where n grows proportionally with k or where k stays fixed while n increases.

Core claim

The central claim is that the extremal function m_{k,k+1,k+a} equals 2^a whenever a is at most k/2 minus 1, and that this value is attained by explicitly described configurations of k+a points in general position with no empty (k+1)-gon.

What carries the argument

The extremal function m_{k,ℓ,n} that records the largest number of empty k-gons in any n-point set containing no empty ℓ-gon.

If this is right

  • The bound is achieved only by certain extremal configurations whose structure is fully described in the paper.
  • When n equals alpha times k for fixed alpha, the paper supplies matching-style upper and lower bounds on the same function m.
  • For fixed k and n tending to infinity the number of k-holes is at least on the order of n to the floor of k over 3 and at most on the order of n to the ceiling of k over 2 plus 1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The exact power-of-two count for small excess suggests that the allowed configurations are built by successively adding one of two possible positions for each extra point.
  • The polynomial growth rates for large n may connect to known results on the number of empty polygons in sets with bounded convex-layer depth.
  • If the upper bound O(n^{ceil(k/2)+1}) can be improved, it would tighten the gap with the Omega(n^{floor(k/3)}) lower bound.

Load-bearing premise

Absence of every (k+1)-hole plus general position restricts the possible arrangements enough that the number of k-holes cannot exceed 2^a for small a.

What would settle it

A concrete set of k plus a points in general position with no empty (k+1)-gon but strictly more than 2^a empty k-gons, for some a at most k/2 minus 1.

Figures

Figures reproduced from arXiv: 2606.08762 by Adam D\v{z}avoronok, Aleksa D\v{z}uklevski, Alica Dom\'anyov\'a, Martin Andri\v{c}\'ik, Matou\v{s} \v{S}afr\'anek.

Figure 1
Figure 1. Figure 1: Illustration of the cases in the proof of Lemma 2.1, including the case with two points inside. We now proceed with the upper bound argument for mk,k+1,k+a. It follows immediately from the following proposition. Proposition 2.2. Under the assumptions of Theorem 1.1, if K is a fixed k-hole and A = X \ K is the set of remaining a points, then for every B ⊆ A, there is at most one k-hole that contains all the… view at source ↗
Figure 2
Figure 2. Figure 2: Construction depicting sharpness of k ≥ 2a + 2. To finish the proof of Theorem 1.1, we proceed with the lower bound [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The local lower-bound construction for mk,k+1,k+a ≥ 2 a . Proof. By Proposition 2.2, for any subset B ⊆ A, there is at most one k-hole HB such that HB ∩A = B and HB ⊆ K ∪B. Since there are exactly 2a subsets of A and exactly 2a distinct k-holes in X, this bound is perfectly tight. Thus, there is a bijection between the subsets of A and the k-holes of X. For each single-element subset {x} ⊆ A, let H{x} be i… view at source ↗
Figure 4
Figure 4. Figure 4: The described chain construction. For an empty convex 2r-gon K = (v1, . . . , v2r) with indices modulo 2r, we define two sampled r-gons by keeping one vertex and skipping one periodically. For t ∈ {1, 2}, let Q (t) (K) := (vt , vt+2, . . . , vt+2r−2). Each 2r-gon K forms exactly two such r-gons. Notice the structure this imposes on K \ Q: the r skipped vertices must lie exactly one in each of the r exterio… view at source ↗
Figure 5
Figure 5. Figure 5: Local configuration in the proof of Lemma 4.1. We are now ready to finish the proof. Proof of Theorem 1.2. Fix a point set X achieving mk,k+1,n holes of size k without (k + 1) hole. For an empty convex r-gon Q, let N(Q) be the number of valid empty convex 2r-gons K for which Q is a sampled subhole. By our double-counting setup, 2m2r,2r+1,n = X Q N(Q). For a fixed Q, let E be the set of all valid r-tuple ex… view at source ↗
Figure 6
Figure 6. Figure 6: Construction of Horton set and depiction of property being 4-closed from above and below We shall also use the following standard flat perturbation form of the Horton construction [PITH_FULL_IMAGE:figures/full_fig_p014_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Construction for r = 5 We finish again with a brief comment how the case when 3 ∤ k is handled. Let p = k−3⌊ k 3 ⌋. We form r = ⌊ k 3 ⌋ Horton sets from n − p points of size mi ∈ {⌊(n − p)/r⌋, ⌈(n − p)/r⌉}. We arrange these blocks together with a block of the remaining p in ⌈ k 3 ⌉-gon, as in the case above [PITH_FULL_IMAGE:figures/full_fig_p016_7.png] view at source ↗
read the original abstract

We study the maximal number $m_{k,\ell,n}$ of empty convex $k$-gons ($k$-holes) determined by an $n$-point set in the plane in general position that contains no empty convex $\ell~$-gon, focusing on the first nontrivial case $\ell=k+1$. Our main result determines the exact value in the small-excess regime: for $n=k+a$ with $a\le k/2-1$, we prove $m_{k,k+1,k+a}=2^a.$ We also describe the extremal configurations attaining equality. Beyond this exact range, we provide upper and lower bounds in the proportional regime $n=\alpha k$ and in the regime where $k$ is fixed and $n$ goes to infinity. In the last mentioned regime we prove that $m_{k,k+1,n}=\Omega_k(n^{\lfloor\frac{k}{3}\rfloor})$ and $m_{k,k+1,n}=O_k(n^{\lceil\frac{k}{2}\rceil+1}).$

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper defines m_{k,ℓ,n} as the maximum number of empty convex k-gons in an n-point set in the plane in general position with no empty ℓ-gon, and focuses on the case ℓ=k+1. Its central result is the exact determination m_{k,k+1,k+a}=2^a for a≤k/2−1 together with an explicit description of the extremal point sets attaining the bound; it further supplies asymptotic upper and lower bounds in the regimes n=αk and fixed k with n→∞ (specifically Ω_k(n^{⌊k/3⌋}) and O_k(n^{⌈k/2⌉+1})).

Significance. If the exact count holds, the result supplies a clean combinatorial classification in the small-excess regime and explicit extremal examples, which is a substantive contribution to the study of holes in point sets. The growth-rate bounds for larger n are consistent with known techniques in the area and add quantitative information.

minor comments (4)
  1. [§2] §2, Definition 2.1: the phrase 'in general position' is used before its precise meaning (no three collinear) is stated; move the definition earlier or cross-reference it.
  2. [Theorem 1.1] Theorem 1.1: the statement of the extremal configurations would benefit from a short illustrative figure for a=2 or a=3 showing the two choices per added point.
  3. [§4.2] §4.2, proof of the upper bound: the induction step invokes a charging argument whose base case for a=0 is only sketched; a one-sentence recap of the a=0 case would improve readability.
  4. [§5] The O_k(n^{⌈k/2⌉+1}) bound in the large-n regime is stated without an explicit reference to the underlying convex-layer or order-type argument; adding a one-line pointer to the relevant lemma would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the accurate summary of our results, and the recommendation for minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; direct combinatorial classification

full rationale

The central result m_{k,k+1,k+a}=2^a is obtained by explicit classification of admissible point sets under the no-(k+1)-hole condition plus general position. The abstract and reader's summary indicate a direct proof that enumerates extremal configurations attaining equality, with no fitted parameters, no self-citation chains, and no reduction of the claimed equality to its own inputs by construction. The derivation therefore remains self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard domain assumptions from discrete geometry with no free parameters or invented entities mentioned.

axioms (2)
  • domain assumption Point sets are in general position (no three collinear).
    Standard assumption to ensure convexity and emptiness are well-defined without degeneracies.
  • standard math A k-hole is defined as an empty convex k-gon spanned by the points.
    Core definition in the study of holes in point sets.

pith-pipeline@v0.9.1-grok · 5761 in / 1239 out tokens · 28892 ms · 2026-06-27T18:06:03.532551+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    A superlinear lower bound on the number of 5-holes.Journal of Combinatorial Theory, Series A, 173:105236, 2020

    Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kynˇ cl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber. A superlinear lower bound on the number of 5-holes.Journal of Combinatorial Theory, Series A, 173:105236, 2020

    2020

  2. [2]

    There are many 5-holes, 2026

    Omar Astudillo-Marb´ an and Oriol Sol´ e-Pi. There are many 5-holes, 2026

    2026

  3. [3]

    Empty simplices in euclidean space.Canadian Math- ematical Bulletin, 30(4):436–445, 1987

    Imre B´ ar´ any and Zolt´ an F¨ uredi. Empty simplices in euclidean space.Canadian Math- ematical Bulletin, 30(4):436–445, 1987

    1987

  4. [4]

    Planar point sets with a small number of empty convex polygons.Studia Scientiarum Mathematicarum Hungarica, 41(2):243–266, 2004

    Imre B´ ar´ any and Pavel Valtr. Planar point sets with a small number of empty convex polygons.Studia Scientiarum Mathematicarum Hungarica, 41(2):243–266, 2004

    2004

  5. [5]

    PhD thesis, Uni- versit¨ at Bonn, 1987

    Klemens Dehnhardt.Leere konvexe Vielecke in ebenen Punktmengen. PhD thesis, Uni- versit¨ at Bonn, 1987

    1987

  6. [6]

    Some more problems on elementary geometry.Australian Mathematical Society Gazette, 5(2):52–54, 1978

    Paul Erd˝ os. Some more problems on elementary geometry.Australian Mathematical Society Gazette, 5(2):52–54, 1978

    1978

  7. [7]

    A combinatorial problem in geometry.Compositio Mathematica, 2:463–470, 1935

    Paul Erd˝ os and George Szekeres. A combinatorial problem in geometry.Compositio Mathematica, 2:463–470, 1935

    1935

  8. [8]

    Empty convex hexagons in planar point sets.Discrete & Computational Geometry, 39(1–3):239–272, 2008

    Tobias Gerken. Empty convex hexagons in planar point sets.Discrete & Computational Geometry, 39(1–3):239–272, 2008. doi: 10.1007/s00454-007-9018-x

    work page doi:10.1007/s00454-007-9018-x 2008

  9. [9]

    Konvexe f¨ unfecke in ebenen punktmengen.Elemente der Mathematik, 33:116–118, 1978

    Heiko Harborth. Konvexe f¨ unfecke in ebenen punktmengen.Elemente der Mathematik, 33:116–118, 1978

    1978

  10. [10]

    Marijn J. H. Heule and Manfred Scheucher. Happy ending: An empty hexagon in every set of 30 points. InTools and Algorithms for the Construction and Analysis of Systems, volume 14570 ofLecture Notes in Computer Science, pages 61–80. Springer, Cham, 2024. doi: 10.1007/978-3-031-57246-3 5

    work page doi:10.1007/978-3-031-57246-3 2024

  11. [11]

    Joseph D. Horton. Sets with no empty convex 7-gons.Canadian Mathematical Bulletin, 26(4):482–484, 1983. doi: 10.4153/CMB-1983-077-8

    work page doi:10.4153/cmb-1983-077-8 1983

  12. [12]

    On empty triangles determined by points in the plane.Acta Mathematica Hungarica, 51(3–4):323–328, 1988

    Meir Katchalski and Amram Meir. On empty triangles determined by points in the plane.Acta Mathematica Hungarica, 51(3–4):323–328, 1988

    1988

  13. [13]

    Springer, 2002

    Jiˇ r´ ı Matouˇ sek.Lectures on Discrete Geometry. Springer, 2002. doi: 10.1007/ 978-1-4613-0039-7

    2002

  14. [14]

    Nicol´ as

    Carlos M. Nicol´ as. The empty hexagon theorem.Discrete & Computational Geometry, 38(2):389–397, 2007. doi: 10.1007/s00454-007-1343-6

    work page doi:10.1007/s00454-007-1343-6 2007

  15. [15]

    Finding sets of points without empty convex 6-gons.Discrete & Com- putational Geometry, 29(1):153–158, 2002

    Mark Overmars. Finding sets of points without empty convex 6-gons.Discrete & Com- putational Geometry, 29(1):153–158, 2002

    2002

  16. [16]

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

    Andrew Suk and Su Zhou. On the maximum number ofk-holes in point sets with no (k+ 1)-hole, 2026. URLhttps://arxiv.org/abs/2606.05721. 18 M. ANDRI ˇCIK, A. DOM ´ANYOV´A, A. D ˇZAVORONOK, A. DˇZUKLEVSKI, AND M. ˇSAFR´ANEK Department of Applied Mathematics, F aculty of Mathematics and Physics, Charles Uni- versity, Czech Republic Email address:martin.andrici...

    work page internal anchor Pith review Pith/arXiv arXiv 2026