Ramsey numbers for empty convex polygons
C. Bautista-Santiago, Javier Cano, Ruy Fabila‐Monroy, Carlos Hidalgo-Toscano, Clemens Huemer, Jesús Leaños, Toshinori Sakai, Jorge Urrutia · 2015
We study a geometric Ramsey type problem where the vertices of the complete graph Kn are placed on a set S of n points in general position in the plane, and edges are drawn as straight-line segments. We define the empty convex polygon Ramsey number REC(k, k) as the smallest number n such that for every set S of n points and for every two-coloring of the edges of Kn drawn on S, at least one color class contains an empty convex k-gon. A polygon is empty if it contains no points from S in its interior. We prove 17 ≤ REC(3, 3) ≤ 463 and 57 ≤ REC(4, 4). Further, there are three-colorings of the edges of Kn (drawn on a set S) without empty monochromatic triangles. A related Ramsey number for islands in point sets is also studied. 1