Three-chromatic geometric hypergraphs

12/03/2021
by   Gábor Damásdi, et al.
0

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 such that there is no translate of C containing at least m points of P, 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset