Almost Empty Monochromatic Polygons in Planar Point Sets
Abstract
For integers r ≥ 3, c ≥ 2, and s ≥ 0, let Mr⋆(c,s) denote the smallest integer such that any set of at least Mr⋆(c,s) points in the plane in general position (no three on a line), colored with c colors, contains a monochromatic r-gon (not necessarily convex) with at most s interior points. Define λr⋆(c) to be the smallest integer such that Mr⋆(c,λr⋆(c)) < ∞. The case of triangles, that is, r=3, has been studied in recent years. In this paper, we establish bounds on λr⋆(c), for r ≥ 4. Specifically, in the bichromatic case, we prove that λr⋆(2)≤ ⌊(r−2)/2⌋, for every r≥3. For hexagons, we sharpen this bound to λ6⋆(2)≤1, that is, every sufficiently large bichromatic planar point set in general position contains a monochromatic hexagon with at most one interior point. Next, for any number of colors c≥3 and r≥3, we show that (r − 2) ⌊ (c−1)/2 ⌋ ≤ λr⋆(c) ≤ (r−2)(c−2)+⌊(r−2)δc⌋, for some constant δc ∈ (0, 1/2], depending on c. The upper bounds combine spiral polygonizations with nested convex-hull arguments and, in the hexagon case, incidence counting in $4$-connected triangulations. The lower bounds follow from colored Horton-set constructions.
Related
- Almost Empty Monochromatic Triangles With Many Colors
- Almost Linear Universal Point Sets for Planar Graphs
- Large Planar Point Sets Contain 4 Collinear Points or Almost 7-Cliques, and Related Results
- Monochromatic triangles with empty intersection and Kneser Ramsey numbers
- Monochromatic Almost-Pythagorean Quadruples
BibTeX
@misc{bhattacharya2026almost,
title = {{Almost Empty Monochromatic Polygons in Planar Point Sets}},
author = {Bhaswar B. Bhattacharya and Sandip Das and Sk Samim Islam and Aashirwad Mohapatra and Saumya Sen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23920},
eprint = {2610.23920},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23920},
}
RIS
TY - UNPB
TI - Almost Empty Monochromatic Polygons in Planar Point Sets
AU - Bhaswar B. Bhattacharya
AU - Sandip Das
AU - Sk Samim Islam
AU - Aashirwad Mohapatra
AU - Saumya Sen
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.23920
UR - https://arxiv.org/abs/2610.23920
AB - For integers r ≥ 3, c ≥ 2, and s ≥ 0, let M_r^⋆(c,s) denote the smallest integer such that any set of at least M_r^⋆(c,s) points in the plane in general position (no three on a line), colored with c colors, contains a monochromatic r-gon (not necessarily convex) with at most s interior points. Define λ_r^⋆(c) to be the smallest integer such that M_r^⋆(c,λ_r^⋆(c)) < ∞. The case of triangles, that is, r=3, has been studied in recent years. In this paper, we establish bounds on λ_r^⋆(c), for r ≥ 4. Specifically, in the bichromatic case, we prove that λ_r^⋆(2)≤ ⌊(r−2)/2⌋, for every r≥3. For hexagons, we sharpen this bound to λ_6^⋆(2)≤1, that is, every sufficiently large bichromatic planar point set in general position contains a monochromatic hexagon with at most one interior point. Next, for any number of colors c≥3 and r≥3, we show that (r − 2) ⌊ (c−1)/2 ⌋ ≤ λ_r^⋆(c) ≤ (r−2)(c−2)+⌊(r−2)δ_c⌋, for some constant δ_c ∈ (0, 1/2], depending on c. The upper bounds combine spiral polygonizations with nested convex-hull arguments and, in the hexagon case, incidence counting in $4$-connected triangulations. The lower bounds follow from colored Horton-set constructions.
ER -