Three-chromatic geometric hypergraphs

Abstract

We prove that for any planar convex body $C$ there is a positive integer $m$ with the property that any finite point set $P$ in the plane can be three-colored in such a way that no translate of $C$ contains $m$ points of $P$ (or more), all of the same color. As a part of the proof, we show a strengthening of the Erdős–Sands–Sauer–Woodrow conjecture. Surprisingly, the proof also relies on the two-dimensional case of the Illumination Conjecture. The extended abstract of this paper already appeared in the proceedings of SoCG ’22.