2026/03/05 by Oswin Aichholzer, Helena Bergold, Simon D. Fink +3 · 1 voice
Computer Science · Mathematics · #Colored #Computational Geometry and Mesh Generation #General position #Limits and Structures in Graph Theory #Monochromatic color #Plane (geometry) #Point (geometry) #Point processes and geometric inequalities #Position (finance) #Regular polygon #cs.CG
paper · pdf · doi:10.48550/arxiv.2603.05339
openalex publication_date 2026/03/05 · arxiv published 2026/03/05 · arxiv updated 2026/03/05 · openalex created_date 2026/03/07 · openalex updated_date 2026/07/28
We consider colored variants of a class of geometric-combinatorial questions on k-gons and empty k-gons that have been started around 1935 by Erdős and Szekeres. In our setting we have n points in general position in the plane, each one colored either red or blue. A structure on k points is a geometric graph where the edges are spanned by (some of) these points and is called monochromatic if all k points have the same color. Already for k=4 there exist interesting open problems. Most prominently, it is still open whether for any sufficiently large bichromatic set there always exists a convex empty, monochromatic quadrilateral. In order to shed more light on the underlying geometry we study the existence of five different monochromatic structures that all use exactly 4 points of a bichromatic point set. We provide several improved lower and upper bounds on the smallest n such that every bichromatic set of at least n points contains (some of) those monochromatic structures.